itertools: 組合せ論
順列、組合せ、直積を生成します。
「itertools: 組合せ論」はCoddyKit上の無料Python Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはPython Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Python Academyコースには全4レッスンが含まれています。
組合せ計算の概要
itertoolsは、4つの組合せ計算用関数、product、permutations、combinations、combinations_with_replacementを提供します。
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()
product(*iterables, repeat=1)は直積を計算します。これは、入れ子のforループと同等です。
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()
permutations(it, r)は、長さrの順序付き配列をすべて生成します。総数はP(n,r) = n!/(n-r)!です。
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)) # 6combinations()
combinations(it, r)は、重複なしで長さrの順序を考慮しない選択をすべて生成します。総数はC(n,r) = n!/(r!(n-r)!)です。
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)) # 6combinations_with_replacement()
combinations_with_replacement(it, r)では、組合せの中に同じ要素を複数回含めることができます。
import itertools
result = list(itertools.combinations_with_replacement("AB", 2))
print(result)
# [(A,A),(A,B),(B,B)]実体化せずに数える
数えるだけの場合は、すべての要素を生成する代わりにmath.perm、math.comb、またはlen()のショートカットを使ってください（有限の結果で利用できます）。
import math
print(math.perm(10, 3)) # 720
print(math.comb(10, 3)) # 120パスワードとキーの生成
組合せ計算用のイテレーターを使うと、すべてをメモリに読み込まずに、候補キーやテストケースを生成できます。
import itertools, string
chars = string.ascii_lowercase
# All 2-char lowercase combos:
for combo in itertools.combinations(chars, 2):
pass # process without materialisingproductによるグリッド座標
product(range(rows), range(cols))を使うと、入れ子のループなしで2次元グリッドを反復処理できます。
import itertools
for row, col in itertools.product(range(3), range(3)):
print(f"({row},{col})", end=" ")すべての部分集合のテスト
0からnまでの各長さについてcombinationsを反復処理すると、リストのすべての部分集合を生成できます。
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)combinationsによる重複排除
combinationsを使うと、要素の各ペアをちょうど1回だけ比較できるため、(a,b)と(b,a)のような重複した比較を避けられます。
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}")パフォーマンスに関する注意点
組合せ計算の数列は非常に速く増加します。permutations(range(12))は4億7900万件の結果を生成します。必ずジェネレーターを使い、必要な分だけ実体化してください。
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クイックチェック
コレクションから、重複なしの順序を考慮しないペアをすべて生成するitertools関数はどれですか。
まとめ
直積にはproduct、順序付き配列にはpermutations、順序を考慮しない部分集合にはcombinations、要素の重複を許可する場合にはcombinations_with_replacementを使います。組合せ計算用のイテレーターは、必ず遅延評価で処理してください。
よくある質問
「itertools: 組合せ論」レッスンは無料ですか？
はい。「itertools: 組合せ論」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Python Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Python Academyコースには全4レッスンが含まれています。
「itertools: 組合せ論」で何を学びますか？
順列、組合せ、直積を生成します。 ブラウザで直接実行するハンズオンコードでPython Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Python Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのPython Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「itertools: 組合せ論」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このPython Academyレッスンでコードを書いて実行できますか？
はい。すべてのPython Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- itertools: 無限イテレーターと有限イテレーター
- itertools: 組合せ論
- functools: partial と reduce
- functools: lru_cache と cached_property