# 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:

`product`

`permutations`

`combinations`

`combinations_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)