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)
If you found this article useful, you might be interested in the book Python Quick Start or other books by the same author.

Prev

Popular tags

2d arrays abstract data type alignment and animation arc array arrays behavioural pattern bezier curve built-in function callable object chain circle classes clipping close closure cmyk colour combinations comparison operator comprehension context context manager conversion count creational pattern data types design pattern device space dictionary drawing duck typing efficiency ellipse else encryption enumerate fill filter font font style for loop function function composition function plot functools game development generativepy tutorial generator geometry gif gradient greyscale higher order function hsl html image image processing imagesurface immutable object index inner function input installing iter iterable iterator itertools l system lambda function len line linear gradient linspace list list comprehension logical operator lru_cache magic method mandelbrot mandelbrot set map monad mutability named parameter numeric python numpy object open operator optional parameter or partial application path pattern permutations polygon positional parameter print pure function python standard library radial gradient range recipes rectangle recursion reduce repeat rgb rotation roundrect scaling sector segment sequence setup shape singleton slice slicing sound spirograph sprite square str stream string stroke structural pattern subpath symmetric encryption template text text metrics tinkerbell fractal transform translation transparency triangle tuple turtle unpacking user space vectorisation webserver website while loop zip