itertools: Kombinatorik

Überblick über Kombinatorik

import itertools

# All orderings of 2 items from ABC
print(list(itertools.permutations("ABC", 2)))
# [(A,B),(A,C),(B,A),(B,C),(C,A),(C,B)]

product()

import itertools

print(list(itertools.product([1,2], ["a","b"])))
# [(1,"a"),(1,"b"),(2,"a"),(2,"b")]

# repeat=2 pairs each element with itself
print(list(itertools.product(range(2), repeat=2)))
# [(0,0),(0,1),(1,0),(1,1)]

permutations()

import itertools

result = list(itertools.permutations([1,2,3], 2))
print(result)
# [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]
print(len(result))  # 6

combinations()

import itertools

result = list(itertools.combinations([1,2,3,4], 2))
print(result)
# [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
print(len(result))  # 6

combinations_with_replacement()

import itertools

result = list(itertools.combinations_with_replacement("AB", 2))
print(result)
# [(A,A),(A,B),(B,B)]

Zählen ohne Materialisierung

import math

print(math.perm(10, 3))   # 720
print(math.comb(10, 3))   # 120

Passwort-/Schlüsselgenerierung

import itertools, string

chars = string.ascii_lowercase
# All 2-char lowercase combos:
for combo in itertools.combinations(chars, 2):
    pass  # process without materialising

Gitterkoordinaten mit product

import itertools

for row, col in itertools.product(range(3), range(3)):
    print(f"({row},{col})", end=" ")

Alle Teilmengen testen

import itertools

items = [1, 2, 3]
all_subsets = []
for r in range(len(items)+1):
    all_subsets.extend(itertools.combinations(items, r))
print(all_subsets)

Duplikate mit combinations vermeiden

import itertools

words = ["apple","apricot","banana","blueberry"]
for a, b in itertools.combinations(words, 2):
    if a[0] == b[0]:
        print(f"Same letter: {a}, {b}")

Überlegungen zur Performance

import itertools, math

n = 12
print(f"P(12,12) = {math.factorial(n):,}")   # 479,001,600
# Never: list(itertools.permutations(range(12)))
# Instead: iterate lazily and break early

Schnelltest

Zusammenfassung