Combinatoric iterators from itertools

Batteries included is a blog series about the Python Standard Library. Each day, I share insights, ideas and examples for different parts of the library. Blaugust is an annual blogging festival in August where the goal is to write a blog post every day of the month.

Alongside collections module, one of my favourite collections of tooling in Python’s standard library live in the itertools module. Today, I’ll discuss the four combinatoric iterators that the module offers and how to use them.

The four iterators are product, permutations, combinations and combinations with replacements. If you’re not much into math and don’t know what they mean, that’s totally fine. Every time I need to use one of them, I need to read through the docs to remember which one I need because they are all very similar but they have significant differences.

All of these four return generators making them memory effective but they grow in size real fast so if be cautious if using them with large iterables or iterables of unknown size.

Product

itertools.product creates a cartesian product from its iterables. Cartesian product is a math term that kinda means “combine everything with everything”:

from itertools import product

p = product('1234', 'abcd')
print(list(p))
# [
#  ('1', 'a'), ('1', 'b'), ('1', 'c'), ('1', 'd'), 
#  ('2', 'a'), ('2', 'b'), ('2', 'c'), ('2', 'd'),
#  ('3', 'a'), ('3', 'b'), ('3', 'c'), ('3', 'd'), 
#  ('4', 'a'), ('4', 'b'), ('4', 'c'), ('4', 'd')
# ]

Here we provided product two iterables: a string '1234' and a string 'abcd' and the outcome is every character from the first string paired with every character from the second one.

This is handy when you need to find all the possible combinations but the size of the output grows real fast as the length of the output is the product of the lengths of two inputs.

Permutations

itertools.permutations differs from product in that it only takes in one iterable and an optional number that defines how long permutations is to be generated.

from itertools import permutations

p = permutations('1234', 3)
print(list(p))
# [
#  ('1', '2', '3'), ('1', '2', '4'), ('1', '3', '2'), 
#  ('1', '3', '4'), ('1', '4', '2'), ('1', '4', '3'), 
#  ('2', '1', '3'), ('2', '1', '4'), ('2', '3', '1'),
#  ('2', '3', '4'), ('2', '4', '1'), ('2', '4', '3'),
#  ('3', '1', '2'), ('3', '1', '4'), ('3', '2', '1'),
#  ('3', '2', '4'), ('3', '4', '1'), ('3', '4', '2'),
#  ('4', '1', '2'), ('4', '1', '3'), ('4', '2', '1'),
#  ('4', '2', '3'), ('4', '3', '1'), ('4', '3', '2')
# ]

Permutations are handy if you have for example a list of friends and want to create all possible pairings – or for creating a round robin style pairings for a tournament.

Combinations

itertools.combinations takes similar arguments as permutations: an iterable and a number.

from itertools import combinations

p = combinations('1234', 3)
print(list(p))
# [
#  ('1', '2', '3'), ('1', '2', '4'), 
#  ('1', '3', '4'), ('2', '3', '4')
# ]

The difference between combinations and permutations is that each combination of items only appears in the result once disregarding the positions, effectively treating them as sets when it compares uniqueness.

Combinations with replacement

A special case of combinations is itertools.combinations_with_replacement that works just as combinations but it allows individual items in the iterable to be repeated more than once.

You can imagine it as a bowl of balls with characters in them. When running combinations, for each combination, a ball is removed from the bowl when added to the combination. With combinations_with_replacement, the ball is put back to the bowl.

from itertools import combinations_with_replacement

p = combinations_with_replacement('1234', 3)
print(list(p))
# [
#  ('1', '1', '1'), ('1', '1', '2'), ('1', '1', '3'),
#  ('1', '1', '4'), ('1', '2', '2'), ('1', '2', '3'),
#  ('1', '2', '4'), ('1', '3', '3'), ('1', '3', '4'),
#  ('1', '4', '4'), ('2', '2', '2'), ('2', '2', '3'),
#  ('2', '2', '4'), ('2', '3', '3'), ('2', '3', '4'),
#  ('2', '4', '4'), ('3', '3', '3'), ('3', '3', '4'), 
#  ('3', '4', '4'), ('4', '4', '4')
# ]