順列（N:ラベルあり K:ラベルあり）

単射としての順列と個数の計算

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

問題2

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

写像からみた順列

順列について写像の視点から理解し、関数を使い個数を求め生成します。

写像から見た順列の考え方

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

順列の個数を計算する関数

順列、組み合わせの計算式と標準ライブラリなどによる個数の計算

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

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

順列の個数の計算

$\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 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個}}$

$\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ライブラリのspecial サブモジュールにあるperm関数により順列の場合の数を計算することができます。このほかPythonバージョン3.8以降ではmathモジュールにもperm関数が追加されました。ここでは順列に関する関数をご紹介しますが、ついでに組み合わせに関わる関数についてもご紹介しておきます。

math関数、SciPyライブラリを使い順列の個数を計算する

from scipy.special import perm, comb
import math
print(f'scipy.special.perm(2, 5) = {perm(n, len(k_list), exact = True)}')
print(f'scipy.special.comb(2, 5) = {comb(n, len(k_list), exact = True)}')
print(f'math.perm(2, 5) = {math.perm(n, len(k_list))}')
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となることが必要です。

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

def factorial(n, r=None):
if r is None:
r = n
result = 1
for i in range(n, n-r, -1):
result *= i
return result
def P(k, n):
if k < n:
return 0
return factorial(k, n)
def C(k, n):
if k < n:
return 0
return factorial(k, n) // factorial(n)
print(f'0!={factorial(0)} 1!={factorial(1)} 5!={factorial(5)} 5X4X3={factorial(5,3)}')
print(f'5P5={P(5,5)} 5P3={P(5,3)} 5P1={P(5,1)} 5P0={P(5,0)} 5P6={P(5,6)}')
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が正の整数であれば、階乗、順列、組合せの計算が正しくできることがわかりました。

順列を生成する関数

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

Pythonの標準モジュールであるitertoolsモジュールのpermutations関数により、順列を生成することができます。引数は重複順列と同様です。

itertoolsモジュールによる順列のリストの作成

k_list = ['A', 'B', 'C', 'D', 'E']
n = 3
itertools_perm_list = list(itertools.permutations(k_list,n))
print('itertools.permutations(5, 3) = ',len(itertools_perm_list ))
pprint.pprint(itertools_perm_list)

itertools.permutations(5, 3) =  60
[('A', 'B', 'C'),
 ('A', 'B', 'D'),
 （中略）
('E', 'D', 'A'),
 ('E', 'D', 'B'),
 ('E', 'D', 'C')]

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

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

重複がない集合から順列を生成する関数

順列を生成する関数を作成します。順列は単射になるのでperm_injective_funcという関数名にします。重複順列を生成するperm_unrestricted_func関数とほぼ同じ流れになりますが、単射にするため、itemをelmに結合する時点で先客がいる場合、候補から外れるのでarrayに追加しないようにします。

順列を生成する関数

引　数

k_list

集合Kの要素をタプルで指定

集合Nの要素の個数を指定

返り値

perm_unrestricted_list

順列を2重リスト形式で返す。

引　数

k_list

集合Kの要素をタプルで指定

引　数

集合Nの要素の個数を指定

返り値

perm_injective_list

順列を2重リスト形式で返します。

def perm_injective_func(k_list, n):
array = [()]
for cnt in range(n):
temp = array
array = []
for elm in temp:
for item in k_list:
if item not in elm:
array.append(elm + (item,))
return array
k_list = ['A', 'B', 'C', 'D', 'E']
n = 3
perm_injective_list = perm_injective_func(k_list, n)
print('unrestricted count = ',len(k_list)**n,'perm_injective_func(3, 5) = ',len(perm_injective_list))
if perm_injective_list == itertools_perm_list:
print('perm_injective_list == itertools_perm_list')

unrestricted count =  125 perm_injective_func(3, 5) =  60
perm_injective_list == itertools_perm_list

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

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

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

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

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

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

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

k_list = ['A', 'A', 'A', 'B', 'B']
n = 3
itertools_perm_dup_list = list(itertools.permutations(k_list,n))
perm_injective_dup_list = perm_injective_func(k_list, n)
print('itertools.permutations(3, 5) with duplication = ',len(itertools_perm_dup_list))
print('perm_injective_func(3, 5) with duplication = ',len(perm_injective_dup_list))

itertools.permutations(3, 5) with duplication =  60
perm_injective_func(3, 5) with duplication =  0

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

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

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

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

順列を生成するperm_injective_func関数を重複する要素がある集合にも対応できるよう工夫しmultinomial_by_perm_func関数を作成します。

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

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

def perm_injective_dup_func(k_list, n):
perm_seq = []
for elm in perm_injective_func(range(len(k_list)),n):
perm_seq.append(tuple([k_list[i] for i in elm]))
return perm_seq
k_list = ['A', 'A', 'A', 'B', 'B']
n = 3
perm_injective_dup_list = perm_injective_dup_func(k_list, n)
print('unrestricted count = ',len(k_list)**n,'perm_injective_dup_func(3, 5) = ',len(perm_injective_list))
if perm_injective_dup_list == itertools_perm_dup_list:
print('perm_injective_dup_list == itertools_perm_dup_list')

unrestricted count =  125 perm_injective_dup_func(3, 5) =  60
perm_injective_dup_list == itertools_perm_dup_list

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

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

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

多項定理による順列

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

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

問題

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

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

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

$\displaystyle \frac{7!}{3! \cdot 2! \cdot 2!}=210$

重複要素を含む順列は次の数式で計算することができます。

重複要素を含む順列の個数

$n=p_1 + p_2 + p_3 + \cdots + p_k$

$\displaystyle \frac{n!}{p_1! \cdot p_2! + \cdot p_3! + \cdots + p_k!}$

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

重複する要素がある順列を生成し、同じ順列がある場合は1つにまとめることにより、多項定理による順列を生成することができます。

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

def multinomial_by_perm_func(dict):
k_list=[]
for key, value in dict.items():
k_list.extend([key] * value)
array=[]
for elm in perm_injective_dup_func(k_list, len(k_list)):
if elm not in array:
array.append(elm)
return array
dict = {'青':2, '赤':3, '緑':2}
multinomial_by_perm_list = multinomial_by_perm_func(dict)
pprint
len(multinomial_by_perm_list)

[('青', '青', '青', '赤', '赤', '緑', '緑'),
 ('青', '青', '青', '赤', '緑', '赤', '緑'),
 ('青', '青', '青', '赤', '緑', '緑', '赤'),
 ('青', '青', '青', '緑', '赤', '赤', '緑'),
 ('青', '青', '青', '緑', '赤', '緑', '赤'),
 ('青', '青', '青', '緑', '緑', '赤', '赤'),
 ('青', '青', '赤', '青', '赤', '緑', '緑'),

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

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

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