順列

場合の数の中で最もよく使われる順列（permutation）について理解するため、次の問題を考えます。

Example　1.1

3人の学生が合宿でそれぞれ個室に泊まることとします。宿舎には$ K=\{A, B, C, D, E\} $の5部屋が用意されており、学生は出席番号で表し、 $N=\{0, 1, 2\}$としたときの部屋割りとして考えられる順列を一覧にし、その場合の数を計算してください。

個室というところがポイントになります。

単射としての順列と既存のライブラリによる計算

写像からみた順列

こんな時代なのでみんな個室がよい、ということで誰もが同じ部屋に泊まらないような部屋割りも考えられます。写像から見ると、Figure 1.のように、終域に属する要素は全てその定義域の要素にただ1つだけ対応させる単射（injective）になります。

Figure 1.5　単射の対応\p90110_injective.png

既存のライブラリで順列、組み合わせを計算する

順列、組み合わせの計算式

順列はn個からr個を重複なく選ぶと考え ${}_n P_r$ と表記しますが、写像の世界では ${}_k P_n$ とするのが一般的です。はじめに、順列の個数の計算式と、この先使っていく組み合わせの計算式をまとめておきます。

Equation 1.2　順列の個数の計算

$\displaystyle {}_n P_r = \frac{n!}{(n-r)!}=\;\overbrace {n(n-1)(n-2)・・・(n-r+1) \quad}^{r個}$
$\displaystyle {}_n C_r =\frac{ _n P_r}{n!}=\frac{n!}{r!(n-r)!} = \frac{\overbrace {n(n-1)(n-2)\cdots (n-r+1)}^{r個}}{\underbrace {r\times (r-1)\times \cdots 2 \times 1}_{r個}}$
$\displaystyle {}_k P_n = \frac{k!}{(k-n)!}=\;\overbrace {k(k-1)(k-2)・・・(k-n+1) \quad}^{n個}$
$\displaystyle {}_k C_n =\frac{{}_k P_n}{n!}=\frac{k!}{n!(k-n)!} = \frac{\overbrace {k(k-1)(k-2)\cdots (k-n+1)}^{n個}}{\underbrace {n\times (n-1)\times \cdots 2 \times 1}_{n個}}$

SciPyライブラリ、mathモジュールのperm関数による順列の場合の数の計算

順列の数の計算には、SciPyライブラリの scipy.special モジュールで提供される perm 関数を使用します。このほか Python バージョン 3.8 以降では math モジュールにもperm関数が追加されました。組み合わせの数については、次章で詳しく見ていきますが、ここでは数を計算する関数をご紹介しておきます。

Code 1.7　math関数、SciPyライブラリを使い順列、組み合わせの個数を計算する

  1. from scipy.special import perm, comb
  2. import math
  3. print(f'scipy.special.perm(2, 5) = {perm(n, len(k_list), exact = True)}')
  4. print(f'scipy.special.comb(2, 5) = {comb(n, len(k_list), exact = True)}')
  5. print(f'math.perm(2, 5) = {math.perm(n, len(k_list))}')
  6. print(f'math.comb(2, 5) = {math.comb(n, len(k_list))}')
scipy.special.perm(2, 5) = 20
scipy.special.comb(2, 5) = 10
math.perm(2, 5) = 20
math.comb(2, 5) = 10

1.　perm関数、comb関数はSciPyライブラリのscipy.specialモジュールからインポートします。

2.　mathモジュールはモジュール全体をインポートするのが一般的です。

3.　SciPyライブラリのperm関数は組み合わせの数を小数点で返します。整数で戻り値を返すときは、exact = Trueを指定します。

4.　同様に、SciPyライブラリのcomb関数により組み合わせの個数を計算します。

5.　mathモジュールのperm関数は返り値として整数で組み合わせの数を返します。同様に6.においてcomb関数で組み合わせの個数を計算します。

順列、組み合わせを生成する関数を作成

順列、組み合わせの個数を計算する関数を作成しますが、これらの計算では階乗の計算が必要になります。そこで、階乗を計算するfactorial関数を作成し、factorial関数を使って順列を計算するP関数、組み合わせを計算するC関数を作成します。順列と組み合わせはよく使われるので、関数名は英字1文字にします。

階乗：factorial 関数

引数を正の整数nとして、nから1までを掛け合わせます。ただし${}_5 P_3=5\times 4\times 3$のような計算をする場合のように、降順に3つの数字を掛け合わせれば足りることもあります。そこで、2つ目にrという引数を追加し、指定した場合はその個数だけの掛け算とし、指定しない場合には1まで掛け合わせるような工夫をします。なお、0!=1となることも処理に組み込みます。

②順列：P関数

引数として集合Kの個数kと集合Nの個数nを指定します。つまりk個からn個を選んで並べる順列の個数を計算します。P関数は $k \lt p$ の場合は $0$、$n=0$ の場合は1となります。

③：C関数

P関数と同様に組み合わせの個数を計算します。C関数は $k \lt n$ の場合は 0 、$n=0$ の場合は 1 となります。

Code 1.8　階乗、順列、組み合わせを計算する関数

  1. def factorial(n, r=None):
  2. if r is None:
  3. r = n
  4. result = 1
  5. for i in range(n, n-r, -1):
  6. result *= i
  7. return result
  9. def P(k, n):
  10. if k < n:
  11. return 0
  12. return factorial(k, n)
  14. def C(k, n):
  15. if k < n:
  16. return 0
  17. return factorial(k, n) // factorial(n)
  19. print(f'0!={factorial(0)} 1!={factorial(1)} 5!={factorial(5)} 5X4X3={factorial(5,3)}')
  20. print(f'5P5={P(5,5)} 5P3={P(5,3)} 5P1={P(5,1)} 5P0={P(5,0)} 5P6={P(5,6)}')
  21. print(f'5C5={C(5,5)} 5C3={C(5,3)} 5C1={C(5,1)} 5C0={C(5,0)} 5C6={C(5,6)}')
0!=1  1!=1  5!=120  5X4X3=60
5P5=120  5P3=60  5P1=5  5P0=1  5P6=0
5C5=1  5C3=10  5C1=5  5C0=1  5C6=0

1.　2番目の仮引数 $r=None$と指定することにより、rを指定しない場合は初期値でNone、指定した場合はその値がrに代入されます。

2.　1.を受けてrがNoneであれば3.でnをrに代入されます。このことにより、n!の計算ができるようになります。なお、rがNoneであるときの判断は、is演算子を使います。

5.　階乗の計算式は$n\times(n-1)\times(n-2)\times\cdots(n-r+1)$です。この計算を実現するためfor i in range(n, n -r, -1)とします。3つ目の引数が-1の場合、降順にiを回しますが2番目の引数は1つ先まで指定するので、n-rとするとn-r+1で止まります。

9.　順列の計算にはfactorial関数を適用しますが、k < nの場合は0になるように明記します。

$k,n,r$ が正の整数であれば、階乗、順列、組合せの計算が正しくできることがわかりました。

順列を生成する関数

Code 1.9　階乗、順列、組合せを計算する関数

  1. n = 3
  2. k_list = ['A', 'B', 'C', 'D', 'E']
  3. unrestricted_perm_list = generate_unrestricted_perm(k_list, n)
  4. injective_from_unrestricted = []
  5. for perm in unrestricted_perm_list:
  6. if len(perm)==len(set(perm)):
  7. injective_from_unrestricted.append(perm)
  8. injective_from_unrestricted
[('A', 'B', 'C'),
 ('A', 'B', 'D'),
 ('A', 'B', 'E'),
 ('A', 'C', 'B'),
 ('A', 'C', 'D'),

itertoolsモジュールのpermutations関数による順列の生成

順列はPythonの標準モジュールであるitertoolsモジュールが提供するpermutations関数により生成することができます。

Code 1.10　itertoolsモジュールによる順列の生成

  1. itertools_perm_list = list(itertools.permutations(k_list, n))
  2. print('itertools.permutations(5, 3) = ', len(itertools_perm_list))
  3. if itertools_perm_list == injective_from_unrestricted:
  4. print('itertools_perm_list == injective_from_unrestricted')
itertools.permutations(5, 3) =  60
itertools_perm_list == injective_from_unrestricted

2.　itertoolsモジュールのpermutations関数により、順列のリストを出力することができます。

順列の個数は $5\times4\times3=60$ となります。

順列を生成する関数を作成

順列を生成する関数を作成します。順列は単射になるのでgenerete_injective_permという関数名にします。重複順列を生成するgenerete_ unrestricted _perm関数とほぼ同じ流れになりますが、単射にするため、itemをelmに結合する時点すでにk_listの要素が順列に存在する（部屋に先客がいる）場合、候補から外れるのでperm_listに追加しないようにします。

Code 1.11　順列を生成する関数

  1. def generate_injective_perm(k_list, n):
  2. perm_list = [()]
  3. for _ in range(n):
  4. next_perm = []
  5. for elm in perm_list:
  6. for item in k_list:
  7. if item not in elm:
  8. next_perm.append(elm + (item,))
  9. perm_list = next_perm
  10. return perm_list
  13. perm_injective_list = generate_injective_perm(k_list, n)
  14. print(f'unrestricted count = {len(k_list)**n}')
  15. print(
  16. f'generate_injective_perm({len(k_list)}, {n})) ='
  17. f'{len(perm_injective_list)}'
  18. )
  19. if perm_injective_list == itertools_perm_list:
  20. print('perm_injective_list == itertools_perm_list')
unrestricted count =  125
generate_injective_perm(5, 3)) =60
perm_injective_list == itertools_perm_list

8.　if item not in elmの条件文で、入ろうとした部屋に誰かが入っていないかを判断します。

9.　8.により単射の要件を満たす可能性のある場合に限り、elmにitemを結合しperm_listに追加します。

generete_injective_perm関数では、学生1人1人についてリストに追加するときに単射の判断をしていますが、最後の1人のところで判断する方法も考えられます。この場合、8行目の判断の回数が少なくてすむ代わりに、終了直前までperm_listに単射の要件を満たさないタプルも候補として残しておく必要があるので、どちらの効率が良いか一概には言えません。

集合Kに重複する要素がある場合の順列

重複する要素がある場合のitertoolsと自作関数の違い

itertoolsのpermutations関数と#6のgenerete_injective_perm関数を使い、k_list = ['A', 'A', 'A', 'B', 'B']のように要素が重複している場合の順列を生成します。

Code 1.12　重複のある要素から順列を生成する

  1. n = 3
  2. k_list = ['A', 'A', 'A', 'B', 'B']
  3. itertools_perm_dup_list = list(itertools.permutations(k_list,n))
  4. perm_injective_dup_list = generate_injective_perm(k_list, n)
  5. print(
  6. f'itertools.permutations ({len(k_list)}, {n}) with duplication ='
  7. f'{len(itertools_perm_dup_list)}'
  8. )
  9. print(
  10. f'generate_injective_perm({len(k_list)}, {n}) with duplication ='
  11. f'{len(perm_injective_dup_list)}'
  12. )
itertools.permutations(3, 5) with duplication =  60
generete_injective_perm (3, 5) with duplication =  0

3.　itertoolsのpermutationsの結果は、itertools_perm_dup_listというリストに代入します。

4.　同様にgenerete_injective_permの結果はリストperm_injective_dup_listに代入します。

itertoolsの場合は重複する要素が無い場合と同じ個数の順列を生成しましたが、generete_injective_perm関数は0件（空のリスト）になってしまいます。同じ要素があると順列の候補から外してしまうので当然の結果です。重複する要素の順列を作成することが求められることはそう多くはありませんが、次の問題のように多項定理による順列を生成する場合に力を発揮します。

重複する要素がある場合に対応する関数の作成

順列を生成するgenerete_injective_perm関数を重複する要素がある集合にも対応できるように改善した関数を作成します。

新しく作成する関数はgenerete_injective_permと従来の関数に”dup” （duplicateの略）を付け加えた名称にします。この関数では、いったん各要素に仮の番号をつけて順列を生成し、順列の番号を色に置き換えて出力します。順列を生成する部分はgenerete_injective_perm関数を使うので、あらかじめ実行しておく必要があります。

Code 1.13　重複する要素に対応する順列を生成する

  1. def generate_injective_dup_perm(k_list, n):
  2. perm_seq = []
  3. for elm in generate_injective_perm(range(len(k_list)), n):
  4. new_elm = []
  5. for item in elm:
  6. new_elm.append(k_list[item])
  7. perm_seq.append(tuple(new_elm))
  8. return perm_seq
  10. perm_injective_dup_list = generate_injective_dup_perm(k_list, n)
  11. print(f'unrestricted = {len(k_list)**n}')
  12. print(f'injection = {len(perm_injective_dup_list)}')
  13. if perm_injective_dup_list == itertools_perm_dup_list:
  14. print('perm_injective_dup_list == itertools_perm_dup_list')
unrestricted = 125
injection = 60
perm_injective_dup_list == itertools_perm_dup_list

3.　 generete_injective_perm関数を実行するときに、引数k=listを集合Kの要素ではなく、要素の個数の大きさの(range(len(k_list)),n)とします。このことにより、k_listに重複した要素があっても、要素の順番で順列を生成することができます。

5.　最終的には、k_listでの順番から実際の値に変換する必要があるのでk_list[item]としてリストを作り直します。

itertoolsと同じように重複のある順列を生成することができました。つぎにいよいよ多項定理による順列を生成する関数を作成します。引数としては辞書形式で渡して、これをいったんリストに変換したのち、重複のある順列を生成しperm_listに追加しますが、すでに新しいリストにある組み合わせは追加しないようにすることで重複をなくすようにします。

多項定理による順列

多項定理による順列の考え方

多項定理による順列について理解するため、次の問題を考えます。

Example　1.2

青いボールが3個、赤いボールが2個、緑色のボールが2個あります。これらの7個上ボールを一列に並べると、その並べ方は何通りになりますか。ただし、同じ色のボールはそれぞれ区別しないものとします。

意外と難しい問題です。多項定理（multinomial theorem）が何かはさておいて、ここではこの問題に絞って考えます。

7個のボールに対しいったん色を無視して0から6まで番号をつけて、6!=720個の順列を生成します。ところが、このうち3個は青で区別がつかないので、順列の3!通りは同じものとして割り返します。同様に赤が2個なので2!通り、さらに緑が2個なので2!通りを同じものとしてまとめるためます。このため、多項定理による順列の個数は次の通りになります。

$p_1$個、$p_2$個、$p_3$個の区別できない要素からなる順列の総数は多項係数（multinomial coefficient）で表現することができ、ここでは$M(p_1, p_2, p_3)$と定義します。重複要素を含む順列は次の数式で計算することができます。

多項定理による順列を生成する関数

重複する要素がある順列を生成し、同じ順列がある場合は1つにまとめることにより、多項定理による順列を生成することができます。関数名は多項定理からgenerate_multinomial_by_permとします。ここではそれぞれのボールの色を辞書形式で渡し、順列をタプルで生成しリストにまとめます。

Code 1.14　重複要素を含む順列を生成する

  1. def generate_multinomial_by_perm(dict):
  2. k_list = []
  3. for key, value in dict.items():
  4. k_list.extend([key] * value)
  5. perm_list = []
  6. for elm in generate_injective_dup_perm(k_list, len(k_list)):
  7. if elm not in perm_list:
  8. perm_list.append(elm)
  9. return perm_list
  11. dict = {'青': 2, '赤': 3, '緑': 2}
  12. multinomial_by_perm_list = generate_multinomial_by_perm(dict)
  13. print('multinomial_by_perm_list = ', len(multinomial_by_perm_list))
  14. multinomial_by_perm_list
multinomial_by_perm_list =  210

[('青', '青', '青', '赤', '赤', '緑', '緑'),
 ('青', '青', '青', '赤', '緑', '赤', '緑'),
 ('青', '青', '青', '赤', '緑', '緑', '赤'),
 ('青', '青', '青', '緑', '赤', '赤', '緑'),
 　
（中略）

 ('緑', '緑', '赤', '青', '赤', '青', '赤'),
 ('緑', '緑', '赤', '青', '赤', '赤', '青'),
 ('緑', '緑', '赤', '赤', '青', '青', '赤'),
 ('緑', '緑', '赤', '赤', '青', '赤', '青'),
 ('緑', '緑', '赤', '赤', '赤', '青', '青')]

3.　dict={'青':2, '赤':3, '緑':2}をelements=[‘青’, ‘青’, ‘青’, ’赤”, ’赤”, ”緑”, ”緑”]となるようなリストk_listに展開します。色の数の個数分だけリストをコピー、extendメソッドを使い追加します。

6.　 generete_injective_dup_permで生成した重複を含む順列に対して、同じ組み合わせの要素があったときは、新しいリストperm_listに追加しないようにします。

多項定理による順列を生成する関数を生成することができました。しかし、この方法はいったん順列を生成し、そこから多項定理でまとめるので、要素数が多くなるとデータが一時的に膨大になってしまいます。もっと効率的な方法は組み合わせの生成のところで検討します。最後に、SymPyライブラリの関数を使い多項定理による順列を生成し、結果を比べます。

Code 1.15　SymPyライブラリのmultiset_permutations関数による多項展開

  1. from sympy.utilities.iterables import multiset_permutations
  2. sympy_multi_list = list(multiset_permutations(dict))
  3. if sorted([tuple(x) for x in sympy_multi_list]) == sorted(
  4. multinomial_by_perm_list
  5. ):
  6. print('multinomial_by_perm_list == sympy_multi_list')
perm_injective_dup_list == itertools_perm_dup_list

2.　対象とする要素は#7と同じ辞書形式を渡します。なお、リスト形式で渡すこともできます。

elements = ['青', '青', '赤', '赤', '赤', '緑', '緑']

sage_multi_list = list(multiset_permutations(elements))

3.　生成される順列の個数や内容は同じだが順番が異なるので、双方に対してsorted関数を使い並べ替えたのち比較します。

multiset_permutations関数の本来の使い方は別にご紹介することとし、現時点では自作関数が正しく稼働しているかの確認にとどめます。このように順列にはいろいろな発展が考えられます。

ictsr4 All Rights Reserved.