Combinatoric iterators from itertools
![](/assets/img/posts//combinatoric-iterators-from-itertools/combinatoric-iterators-from-itertools-cover.png)
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')
# ]