The Python Journey - Permutations, Combinations, Products and More

Useful Links

Itertools Itertools (GeeksForGeeks)Permutations and Combinations Permutations with Examples Permutations in Python

Page Contents

Overview of Permutations and Combinations
Product
Demonstrating With Code
Rolling Dice Examples
Chain
Cycle
AoC Examples

Overview of Permutations and Combinations

	Permutations	Combinations
What is it?	The number of ways to arrange items	The number of ways to choose items
Ordering	Important	Irrelevant
r items from n items	\(^nP_r = \frac{n!}{(n-r)!}\)	\(^nC_r = \frac{n!}{r!(n-r)!}\)
All 4 items from digits 1,2,3,4	\(^{4}P_4 = \frac{4!}{(4-4)!} = 4! = 24\)	\(^{4}C_4 = \frac{4!}{4!.(4-4)!} = 1\)
All 4 items from digits 1,2,3,4	1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321	1234
3 items from digits 1,2,3,4	\(^{4}P_3 = \frac{4!}{(4-3)!} = 24\)	\(^{4}C_3 = \frac{4!}{3!.(4-3)!} = 4\)
3 items from digits 1,2,3,4	123, 124, 132, 134, 142, 143, 213, 214, 231, 234, 241, 243, 312, 314, 321, 324, 341, 342, 412, 413, 421, 423, 431, 432	123, 124, 134, 234
4 items from digits 0-9	\(^{10}P_4 = \frac{10!}{(10-4)!} = 5040\)	\(^{10}C_4 = \frac{10!}{4!.(10-4)!} = 210\)

Permutations
- A unique arrangement of a group of things.
- Returns unique permutations of items, including their sequence. So, given teh numbers 123, 123 is a different permutation to 321.
Combinations return unique combinations of items, ignoring sequence. It is about members, not order. 123 and 321 are the same.

The number of permutations will be greater than the number of combinations.

Product

We use itertools.product() to obtain the catesian product, i.e. the product of every item from each iterable supplied. If we pass two iterables of length x and y respectively, then the resulting iterable will have length x*y.

Also, we can use product() with the repeat attribute, to obtain the cartesian product of the iterable with itself. E.g. with an iterable of length x repeated n times, the resulting iterable will have length x**n.

This can be a convenient way of way of iterating through multiple dimensions without writing nested loops.

Demonstrating With Code

The itertools package provides both the permutations() and combinations() functions.

from itertools import permutations, combinations

def convert_to_num(num_seq) -> str:
    """ Take a sequence of digits, and convert to a single str """
    return "".join(num_seq)

items = list(str(val) for val in range(1,4+1)) # [1, 2, 3, 4]
SELECTION_SZ = 3
print(f"items = {items}")

print("PERMUTATIONS")

# Get all the ways of ordering all the numbers...
perms = list(permutations(items))
print(f"Count of perms with size {len(items)}: {len(perms)}")
print(",".join(convert_to_num(perm) for perm in perms))

# Get all the ways of ordering 3 numbers from these four digits...
perms = list(permutations(items, SELECTION_SZ))
print(f"Count of perms with size {SELECTION_SZ}: {len(perms)}")
print(",".join(convert_to_num(perm) for perm in perms))

print("\nCOMBINATIONS")

# Get all the ways of picking all the numbers, where order doesn't matter...
combos = list(combinations(items, len(items)))
print(f"Count of combos with size {len(items)}: {len(combos)}")
print(",".join(convert_to_num(combo) for combo in combos))

# Get all the ways of picking 3 numbers from these four digits...
combos = list(combinations(items, SELECTION_SZ))
print(f"Count of combos with size {SELECTION_SZ}: {len(combos)}")
print(",".join(convert_to_num(combo) for combo in combos))

print("\nPRODUCT")

# Get all the ways of picking all the numbers...
prod_items = list(product(items, repeat=3))
print(f"Count of product with size {len(items)} and repeats=3: {len(prod_items)}")
print(",".join(convert_to_num(val) for val in prod_items))

Output:

items = ['1', '2', '3', '4']
PERMUTATIONS
Count of perms with size 4: 24
1234,1243,1324,1342,1423,1432,2134,2143,2314,2341,2413,2431,3124,3142,3214,3241,3412,3421,4123,4132,4213,4231,4312,4321
Count of perms with size 3: 24
123,124,132,134,142,143,213,214,231,234,241,243,312,314,321,324,341,342,412,413,421,423,431,432

COMBINATIONS
Count of combos with size 4: 1
1234
Count of combos with size 3: 4
123,124,134,234

PRODUCT
Count of product with size 4 and repeats=3: 64
111,112,113,114,121,122,123,124,131,132,133,134,141,142,143,144,211,212,213,214,221,222,223,224,231,232,233,234,241,242,243,244,311,312,313,314,321,322,323,324,331,332,333,334,341,342,343,344,411,412,413,414,421,422,423,424,431,432,433,434,441,442,443,4444

Rolling Dice Examples

Imagine rolling two dice.

from itertools import combinations, combinations_with_replacement, product, permutations
 
die = list(range(1, 7))
print(f"One die: {die}")
 
# Cartesian product of throwing 2 dice
cp = list(product(die, repeat=2))
print("\nCARTESIAN PRODUCT")
print("All possible ways of throwing two dice:")
print(f"{cp}\nProduct count={len(cp)}")
 
# All unique permutations (order matters)
perms = list(permutations(die, 2))
print("\nPERMUTATIONS")
print("All unique combinations from two dice. A given number will not be repeated:")
print(f"{perms}\nCount of perms={len(perms)}")
 
# All unique combinations, disallowing the same number twice.  I.e. disallowing re-placement.
combos = list(combinations(die, 2))
print("\nCOMBINATIONS")
print("All unique combinations from two dice, ignoring throwing same on both dice:")
print(f"{combos}\nCount of combos={len(combos)}")
 
# All unique combinations, allowing re-placement
cwr = list(combinations_with_replacement(die, 2))
print("\nCOMBINATIONS WITH REPLACEMENT")
print("All unique combinations from two dice, including throwing same on both dice:")
print(f"{cwr}\nCount of combos={len(cwr)}")

Output:

One die: [1, 2, 3, 4, 5, 6]

CARTESIAN PRODUCT
All possible ways of throwing two dice:
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]    
Product count=36

PERMUTATIONS
All unique combinations from two dice. A given number will not be repeated:
[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), (5, 4), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5)]
Count of perms=30

COMBINATIONS
All unique combinations from two dice, ignoring throwing same on both dice:
[(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]
Count of combos=15

COMBINATIONS WITH REPLACEMENT
All unique combinations from two dice, including throwing same on both dice:
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 3), (3, 4), (3, 5), (3, 6), (4, 4), (4, 5), (4, 6), (5, 5), (5, 6), (6, 6)]
Count of combos=21

There are 36 different outcomes from rolling two dice. These outcomes can be determined using itertools.product(die, repeat=n) where n is the number of dice. This retuns the cartesian product of our two dice.
We can use itertools.permutations(die, n) to get all unique permutations of the two die rolls.
- The results (1,6) and (6,1) are considered two different permutations.
- Note that we only get 30 permutations. This is because permutations do not allow repeating numbers. E.g. it disallows (1,1), (2,2), etc.
- It is possible to determine permutations with repeats. This is in fact equivalent to the cartesian product.
If we ignore order, then (1,2) and (2,1) are the same. We use itertools.combinations(die, n) to determine all these combinations.
- By default, repeating numbers are excluded. E.g. (1,1), (2,2), etc.
- We can allow repeated numbers by using the method combinations_with_replacement(die, 2). This this method gives more combinations.

Chain

We can use itertools.chain(*iterables) to combine multiple iterables into a single iterator, effectively chaining them together into a continuous sequence. It iterates over each iterable in order, one element at a time. We use itertools.chain() when you want to iterate over multiple iterables as if they were a single sequence.

colors = ['red', 'blue']
sizes  = ['small', 'large']

# Chain the two iterables
chained_iterables = itertools.chain(colors, sizes)

# Iterate over the chained iterables and print the elements
for item in chained_iterables:
    print(item)

Output:

red
blue
small
large

Cycle

We use itertools.cycle(iterable) to infinitely iterate through the elements of an iterable. Once we reach the end of the iterale, we start back at the beginning. It returns an infinite generator.

E.g.

colors = ['red', 'green', 'blue']

# Create a cycle iterator from the list
color_cycle = itertools.cycle(colors)

# Iterate over the cycle and print the elements
for _ in range(6):
    print(next(color_cycle))

Output:

red
green
blue
red
green
blue

AoC Examples

‹›