itertools
A lot of "generate every possible X" problems, every pair, every ordering, every combination, can be written as a plain loop or a recursive backtracking function. Python's itertools module already has most of these built and tested, and it's worth knowing what's in there, both to check your own answer and to reach for directly when a problem doesn't actually need you to write the generation logic by hand.
combinations vs permutations
order matters?combinations(iterable, r) gives every group of r items where order doesn't matter. permutations(iterable, r) gives every ordering of r items, so it produces more results:
Both assume you can't reuse the same position twice. combinations_with_replacement(iterable, r) drops that restriction, so an item can pair with itself:
Note
Notice ("a", "a") only shows up in the combinations_with_replacement result. Regular combinations never pairs an element with itself, since it picks each item by position and never revisits a position it already used.
product: the cartesian product
repeat=product() gives every combination of one item from each iterable you pass in, the same thing you'd get from nesting a for loop per iterable:
To combine the same iterable with itself several times, like every length-3 sequence of 0s and 1s, pass repeat= instead of writing the same list out multiple times:
The groupby trap: consecutive keys only
watch outgroupby(iterable) collapses consecutive elements that share the same key into one group. It does not look ahead or behind that run, so the same key showing up again later, separated by something else, starts a brand new group instead of joining the earlier one:
Sort by the same key first and every equal element is guaranteed to be next to every other equal element, so they all land in one group:
Note
The unsorted version above produces three groups: two runs of "a" with a "b" group in between. This is the single most common groupby mistake. If your groups look wrong, check whether the input is sorted by the key you're grouping on before assuming groupby itself is broken.
accumulate: running totals, and chain: flattening
accumulate() returns a running total, the same numbers you'd get by keeping a running sum in a loop:
chain() does the opposite kind of job: it walks several iterables one after another as if they were a single iterable, without actually building a combined list first:
Everything here is a lazy, one-shot iterator
gotchaNone of these functions build a list up front. Each one returns an iterator that produces values on demand, and once you've pulled every value out of it, that same iterator has nothing left to give, even if you iterate over it again:
Note
second_pass comes back empty. first_pass already consumed every value pairs had, and an exhausted iterator doesn't reset itself. If you need to look at the results more than once, wrap the call in list() right away and reuse that list, don't hold onto the raw itertools object and expect to loop over it twice.
Where itertools shows up in interviews
Interviewers almost always want you to build combinations or permutations yourself with recursive backtracking, since that's the pattern being tested. itertools is what you reach for afterward, to sanity-check your own output against the built-in version:
- Subsets asks for every subset of a list, which is exactly what chaining
combinations()across every possible length produces, though the expected solution builds it with backtracking. - Permutations asks for every ordering of a list, the same output
itertools.permutations()returns, again with backtracking as the intended approach.