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 the numbers
123,123is a different permutation to321.
- Combinations return unique combinations of items, ignoring sequence. It is about members, not order.
123and321are 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)wherenis the number of dice. This returns 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.
- The results
- If we ignore order, then
(1,2)and(2,1)are the same. We useitertools.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.
- By default, repeating numbers are excluded. E.g.
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