順列・組合せと数え方
選ぶ順番を区別する場合と、同じ組として扱う場合の件数を学びます。
説明
同じ候補から二つを選ぶ場合でも、役割や順番があるかどうかで件数は変わります。Aを担当、Bを確認者にする配置と、その逆の配置は別ですが、AとBからなる二人組は同じ組です。
このモジュールでは、A・B・C・Dの4候補から2人を選ぶ例を使います。順番を持つ順列と、順番を持たない組合せを列挙し、件数を計算式と照合します。続いて、同じ候補を繰り返し使える場合と、名前の値が重複する場合を扱います。
1異なる役割に二人を配置する
4候補から、担当者と確認者を一人ずつ選びます。同じ人を両方の役割へ置かない条件です。
from itertools import permutations, combinations, product順列・組合せ・直積の機能; people = ['A', 'B', 'C', 'D']候補4人; ordered = list(permutations(people, 2))順番を持つ2人の配置; ordered全配置を表示A/BとB/Aの両方が現れます。一人目を4通りから選び、二人目は残り3通りから選ぶので、順列は12通りです。
2順列の件数を計算する
n候補から異なるr個を順番付きで選ぶ件数は、n!/(n−r)!です。!は、その整数から1までを掛ける階乗を表します。
import math階乗などの数学関数; len(ordered)列挙した件数, math.factorial(4) // math.factorial(4-2)順列の式どちらも12です。4!を2!で割ると4×3だけが残り、順に候補を選んだ計算と一致します。
3役割のない二人組を選ぶ
今度は、同じ二人なら並び順を問わないものとします。
unordered = list(combinations(people, 2))順番を持たない2人組; unordered, len(unordered)全組と件数A/BはありますがB/Aは別に数えず、全部で6通りです。このように順番を付けずに選ぶものを組合せと呼びます。
4組合せでは並べ替え分を除く
二人組には2!=2通りの並びがあります。順列の件数から、この重複分を除きます。
len(ordered) // math.factorial(2)二人の並べ替え分を除く, math.comb(4, 2)組合せ数を求めるどちらも6です。一般にはn!/(r!×(n−r)!)で、選んだr人の並べ替えr!通りを除きます。
5同じ候補を再び選べる場合
今度は二つの位置へ同じ候補を使ってもよいものとします。
repeated = list(product(people, repeat=2))繰り返しを許す2位置の直積; len(repeated)全件数, [pair for pair in repeated if pair[0] == pair[1]]同じ候補を使う組全部で16通りとなり、A/A、B/B、C/C、D/Dの4通りが増えました。それぞれの位置で4通りを独立に選べるため4²です。
6候補を一つも選ばない場合
0人を選ぶ組合せの件数を確認します。
list(combinations(people, 0))0人の組合せを列挙, math.comb(4, 0)件数空の組が一つあり、件数は1です。「何も選ばない」という選び方が一通りあるためです。0通りとは異なります。
7候補の値が重複している場合
候補をA、A、Bに変えます。列挙関数は、同じ値でも一覧の位置が違えば別の候補として扱います。
labels = ['A', 'A', 'B']同じ値を含む候補一覧; positional = list(permutations(labels, 2))位置を区別した順列; positional全結果を表示A/A、A/B、B/Aがそれぞれ重複して現れます。候補の位置を区別した6通りと、表示される名前の組の種類は同じではありません。
8値が同じ組を一つにまとめる
名前の組として異なる種類だけを求めます。
sorted(set(positional))同じ値の組を重複なく表示, len(set(positional))種類の数A/A、A/B、B/Aの3種類です。人を識別したい場合は名前ではなく一意なIDを使うなど、何を同じと数えるかを先に決める必要があります。
まとめ
役割や順番を持つ選び方は順列、順番を持たない選び方は組合せです。候補の再利用を許す場合は件数の計算も変わります。
列挙関数が何を別の候補として扱うかを確認します。位置の異なる候補と、値が異なる候補は同じとは限りません。
操作履歴と解説を振り返れます。
Python 3
from itertools import permutations, combinations, product; people = ['A', 'B', 'C', 'D']; ordered = list(permutations(people, 2)); ordered[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'A'), ('B', 'C'), ('B', 'D'), ('C', 'A'), ('C', 'B'), ('C', 'D'), ('D', 'A'), ('D', 'B'), ('D', 'C')]import math; len(ordered), math.factorial(4) // math.factorial(4-2)(12, 12)
unordered = list(combinations(people, 2)); unordered, len(unordered)([('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')], 6)len(ordered) // math.factorial(2), math.comb(4, 2)(6, 6)
repeated = list(product(people, repeat=2)); len(repeated), [pair for pair in repeated if pair[0] == pair[1]](16, [('A', 'A'), ('B', 'B'), ('C', 'C'), ('D', 'D')])list(combinations(people, 0)), math.comb(4, 0)([()], 1)
labels = ['A', 'A', 'B']; positional = list(permutations(labels, 2)); positional[('A', 'A'), ('A', 'B'), ('A', 'A'), ('A', 'B'), ('B', 'A'), ('B', 'A')]sorted(set(positional)), len(set(positional))([('A', 'A'), ('A', 'B'), ('B', 'A')], 3)演習完了