itertools module - combinatoric iterators
Martin McBride, 2021-10-11
Tags product permutations combinations itertools python standard library
Categories python standard library
The itertools module provides several combinatoric iterators. These functions take one or more input iterables and return an iterator that provides a specific set of combinations of the elements of those iterables.
The functions in this section are:
productpermutationscombinationscombinations_with_replacement
product
product returns the Cartesian product of two or more iterables. See this article for more information on Cartesian products.
Here is an example:
a = [1, 2, 3] b = ['a', 'b', 'c', 'd'] for i in itertools.product(a, b) print(i)
This creates a series of tuples containing every possible combination of a value from a and a value from b:
(1, 'a')(1, 'b'), (1, 'c'), (1, 'd'), (2, 'a'), (2, 'b'), (2, 'c'), (2, 'd'), (3, 'a'), (3, 'b'), (3, 'c'), (3, 'd')
You can think of this as being like a table, where the first iterator defines the rows, the second defines the columns:
Each entry in the table has the value (row, column). The product function generates all the values in the table, in row-major order (ie the first row, then the second row, etc).
Another way to visualise the behaviour of product is to consider a nested loop. This loop demonstrates the order of the pairs created in the example above:
for i in a: for j in b: print(i, j)
product can accept more than two arguments. The nested loop demonstrates this quite nicely. Here is the order you would expect from product(a, b, c) where c is another iterable:
for i in a: for j in b: for k in c: print(i, j, k)
The total length of the output of the product function can be found by multiplying the lengths of all the inputs together. For example, in the original code, a has 3 elements, b has 4 elements, so the result has 12 elements.
product has an optional repeat parameter that can be used to repeat the input elements. It works like this:
product(a, b, repeat=2) # Equivalent to product(a, b, a, b)
This will create 144 elements (3 * 4 * 3 * 4) each being a tuple of 4 elements. The advantage of repeat is that it only reads a and b once. This is useful in cases like this:
a = range(3) b = [10, 20, 30] itertools.product(a, b, a, b) # Zero length result
This will create a zero-length result because it reads a twice. The range function returns an iterator. The first times a is read, it returns the values 0, 1, 2. The iterator has now been exhausted, so when we try to read a a second time it will be empty. A product where one of the inputs is empty will create an empty result. Using repeat avoids this by only reading a one time.
permutations
The permutations function accepts a single iterable and creates every possible permutation of input values. The permutations include every possible ordering of the input values, using each value exactly once. See this article for more information on permutations.
Here is an example:
import itertools a = [1, 2, 3] for i in itertools.permutations(a): print(i)
This creates the following values:
(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
The number of permutations of n elements is n factorial. In this case, the number of elements is 3, so there are 6 permutations.
They are produced in lexicographic order. This means:
- The first element is taken from the input in the order the input elements occur - in this case, 1, then 2, then 3.
- For each first element, the second element is taken from the remaining elements, again in the order they occur.
- And so on.
If the input values are sorted, then the output values will be in sorted order (as they are in this case). However, the algorithm takes no account of the values of the input elements, so if the input values are not sorted the output values will not be in sorted order.
We can supply an optional argument r that defines how many elements to include in the result. This creates a "perm r from n" result:
a = [1, 2, 3, 4] for i in itertools.permutations(a, r=2): print(i)
This code gives us every possible ordering of any 2 items taken from a set of 4 items. The result is:
(1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3)
The number of elements is given by n factorial divided by (n - r) factorial, which is 12 in this case.
In all cases, the permutations treat each element as a unique item, regardless of its value. So if the input has duplicate values, the output will also have duplicate values:
import itertools a = [7, 3, 7] for i in itertools.permutations(a): print(i)
This creates the following values:
(7, 3, 7) (7, 7, 3) (3, 7, 7) (3, 7, 7) (7, 7, 3) (7, 3, 7)
combinations
The combination function returns a sequence of combinations of the values in the input iterable. A combination is every unique set of r elements from the iterable. See this article for more information on combinations.
For example:
a = [1, 2, 3, 4] for i in itertools.combinations(a, r=2): print(i)
This returns:
(1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)
Notice that this list contains (1, 2) but it doesn't contain (2, 1). Combinations do not take account of the order of the values.
combinations_with_replacement
combinations_with_replacement is similar to combinations except that input elements can be repeated. For example:
a = [1, 2, 3, 4] for i in itertools.combinations_with_replacement(a, r=2): print(i)
This adds some extra combinations: (1, 1), (2, 2), (3, 3), and (4, 4):
(1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 3) (3, 4) (4, 4)
