単射としての組み合わせ　

重複順列、順列は区別がある学生を区別がある部屋に割り振る例を考えました。これに対して組み合わせは、区別のないボールを色の区別のある箱に入れるという例を使い考えます。写像にするとラベルがない集合Nにラベルがある集合Kを対応させるという想定です。

Nにラベルを付けない単射としての組み合わせ

組合せの考え方

ラベル有無といってもイメージがわかないので、次の問題を考えます。

問題1

(1) 0から2まで番号が付いた3つのボールを、青、黄、赤、紫、緑の5つの箱に入れるときの順列の数を計算してください。なお、各箱にはボールは1つしか入らないものとします。

(2) 前問でボールに番号がなくラベルがないとしたときの、組み合わせの個数を計算してください。

図表1 で(1)と(2)の違いを写像により表しています。(1)は順列で、$\ _5 P_3 =60$通りになります。(2)はボールのラベルがないことから、(1)では (青、赤、緑)、(青、緑、赤)、(赤、青、緑)、(赤、緑、青)、(緑、赤、青)、(緑、青、赤)の6個の順列を別々に数えたのに対し、(2)の組み合わせでは1通りと計算します。

(2)の組み合わせの個数は、60個の順列を選ばれた３つの箱の順列3!=6で割った10通りになります。この組み合わせは$_k C_n$と表します。

数式2-1　組み合わせの個数の計算　k個から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個}}$

ただし$\ _k C_0=1 \quad k\lt n \rightarrow 0$

組み合わせは順列と同じように箱には球が1つしか入らないので単射となりますが、集合Nはラベルなし（ラベルがついていないものunlabeled）とします。

組み合わせに関する標準ライブラリなどの関数

組み合わせの個数を計算するPythonの関数

組み合わせの個数を計算するために、Pythonの標準ライブラリには、mathモジュール、SciPyライブラリにcomb関数が用意されています。いずれの関数も集合Kの個数kと集合Nの個数nを引数として渡します。

mathモジュール、SciPyライブラリのcomb関数を使い組み合わせの個数を計算する

import math
from scipy.special import comb
k_list = ['青', '赤', '緑', '黄', '紫']
n = 3
print(f'mathモジュールのcomb関数：{math.comb(len(k_list), n)}')
print(f'SciPyパッケージのcomb関数：{comb(len(k_list), n, exact = True)}')

mathモジュールのcomb関数：10
SciPyパッケージのcomb関数：10

1.　mathモジュールは通常、モジュール全体をimportすることが多いようです。

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

3.　mathモジュールのcomb関数は整数で組み合わせの個数をも戻り値として返します。ただし、Pythonの v3.8以降でないと使うことはできません。

4.　scipy.specialパッケージのcomb関数は浮動小数点で返しますが、exact 属性をTrueとすると整数になります。

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

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

①階乗：factorial 関数

引数を正の整数nとして、nから降順に1までを掛け合わせます。ただし$ _ 5 P_3$のような順列の計算をする場合には、はじめの3つを掛ければ済みます。この場合に備えて、2つ目のrという引数を追加し、デフォルトをNoneとしておきます。Noneの場合には1までの階乗を計算すればよいことになります。階乗は0!=1となることが必要です。

②順列：P関数

引数として集合Kの個数kと集合Nの個数nを指定します。つまりk個から選んで並べる順列の個数を計算します。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とすることができます。

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

4.　変数resultを使い、降順に掛け算をすることで階乗を計算します。掛け算の累積の場合には、初期値は1にします。また、このことにより$0!=1$とすることができます。

5.　階乗の計算式は$n\times(n-1)\times(n-2)\times\cdots(n-r+1)$です。この計算を実現するためfor i in range(n, n -r, -1)とします。3つ目の引数は何個おきを示し-1の場合、1つずつの降順となります。2番目の引数は処理をする最後の値より1つ手前までを処理されます。降順の場合にはn-rとするとn-r+1までの計算になります。

9.　順列はfactorial関数を使えば足りますが、k < nの場合は0であることを明記します。

17. 組み合わせは、順列をr!で割ることで計算することができます。

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

組み合わせを生成する関数

itertoolsモジュールのcombinations関数により、組み合わせの一覧を生成することができます。itertoolsはFunction Programming Moduleに分類されます。

引数として集合Kのリストk_listと集合Nの個数nを渡します。

itertoolsモジュールを使い組み合わせの一覧を生成

import itertools
k_list = ['青', '赤', '緑', '黄', '紫']
n = 3
itertools_comb_list = list(itertools.combinations(k_list, n))
print('itertools.combinations(5, 3) = ',len(itertools_comb_list ))
itertools_comb_list

itertools.combinations(5, 3) =  10
[('青', '赤', '緑'),
 ('青', '赤', '黄'),
 ('青', '赤', '紫'),
 ('青', '緑', '黄'),
 ('青', '緑', '紫'),
 ('青', '黄', '紫'),
 ('赤', '緑', '黄'),
 ('赤', '緑', '紫'),
 ('赤', '黄', '紫'),
 ('緑', '黄', '紫')]

1.　itertoolsモジュールはPythonの標準ライブラリですが、ビルドイン関数ではないので、使用する都度、インポートする必要があります。

3.　重複順列はitertoolsモジュールのcombinations関数を使い出力することができます。なお、combinations関数はイテレータという特殊な形式となるので、戻り値をリストとして扱うときにはlist関数を使い変換する必要があります。

4.　出力すると、リストの中に重複順列の各パターンがタプルにまとめられます。件数は10件になります。

6.　生成した重複順列は、pprint関数で出力したほうが見やすくなります。

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

Nに区別がある順列の生成

組み合わせと順列の関係を見るために、前に作成したperm_injective_funcを使い、リストperm_injective_listに順列を生成し、ここから組み合わせcomb_injective_listの配列に集約します。

順列を生成する関数

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 = ['青', '赤', '緑', '黄', '紫']
n = 3
perm_injective_list = perm_injective_func(k_list, n)
print('perm_injective_list(5, 3) = ',len(perm_injective_list))

perm_injective_list(5, 3) =  60

14.　順列を、リストperm_injective_listに代入します。

あえて、出力しませんが次に順列の中から、組み合わせとして絞り込みます。

増加関数としての組み合わせと一覧の生成

増加関数の考え方

組み合わせの一覧を生成するためには、青、赤、緑の3色の順列の6つの中からルールを決めて1つ代表を選ぶ必要があります。最もわかりやすいルールは、図表2のように全ての色に色番号を振り、ボールの順番を$x_0,x_1,x_2 \cdots x_n$というように振る方法です。ボールには区別が無いと言っておきながら違和感を覚えますが、出席番号のような区別ではなく、たまたま選んだ順番という意味として捉えるとわかりやすいと思います。

もし、1番初めに取り出したボール$X_0$が色番号0の青を選んだら、次の$X_1$のボールは0:青の次の1:黄色かそれより大きな色番号から選ぶようにします。もし2:赤を選んだら、$X_2$は3：紫かそれよりも大きな色番号から選びます。この結果、ボールの順番が後になるほど色番号が大きくなる（昇順）ように箱を選ぶこととします。

この考え方によると、#3のように0:青、2:赤、4:緑を選ぶとすると、2:赤、4:緑、0:青のような別の順番の順列は選ばれず、結果として組み合わせを生成することになります。このような考え方を、増加写像(increasing_map)といいます。少しまどろっこしい表現ですが、組み合わせのプログラムを作成するうえで非常に役立ちます。

この関係を数式にするとPythonでは添え字は0から始まりzero-basedといいい図表のようになります。一方、一般的には添え字は1から始まりone-basedといい、次のように表現します。

$1 \leqq x_1\lt x_2\lt x_3 \leqq 5$

組み合わせの式$_k C_n$との対応を考える場合は1から始まる方法のほうが適しているので、2つを併記します。

そこで関係を一般化すると、つぎのようになります。

数式2-2　増加写像を使った組み合わせの表現　$_k C_n$

zero-basedプログラミングでの方法

$0\leqq x_0\lt x_1\lt\cdots\lt x_{n-1}\leqq k-1$

one-based 一般的な考え方

$1 \leqq x_1\lt x_2\lt \cdots \lt x_n \leqq k$

増加関数の考え方を使い順列から組み合わせに変換する

増加写像の考え方を使い組み合わせの一覧を生成する関数を作成します。#4のperm_injective_func関数で作成した順列perm_injective_listから、増加写像の要件を満たす配列のみを抽出する関数を作成し、組み合わせを生成します。関数名は増加写像の意味を込めてincreasing_map_funcとし、引数は順列の配列とします。

順列の配列をelmとして順次読み込み、elmの中の要素よりもその1つ右側の要素の方が大きいことが分かった時点で、そのelmは増加写像の要件を満たさなくなるのでbreakし、次の要素を読み込みます。最後までbreakされなかったelmは、組み合わせとしてリストarrayに追加します。なお、増加関数の絞り込みをするときに、単純に要素同士を比べると文字コード順となりk_listの並び順と一致しなくなるので、k_listのインデックスの順番で比較するようにします。

順列のリストから組み合わせに絞り込む関数

def increasing_map_func(perm_list, k_list):
array=[]
for elm in perm_list:
for i in range(len(elm) - 1):
if k_list.index(elm[i]) >= k_list.index(elm[i + 1]):
break
else:
array.append(elm)
return array
comb_from_perm_list = increasing_map_func(perm_injective_list, k_list)
print('combinations from permutation(5, 3) = ', len(comb_from_perm_list))

combinations from permutation(5, 3) =  10
[('青', '赤', '緑'),
 ('青', '赤', '黄'),
 ('青', '赤', '紫'),
 ('青', '緑', '黄'),
 ('青', '緑', '紫'),
 ('青', '黄', '紫'),
 ('赤', '緑', '黄'),
 ('赤', '緑', '紫'),
 ('赤', '黄', '紫'),
 ('緑', '黄', '紫')]

5.　k_listに対してindexメソッドを適用すると引数の値がk_listの何番目にあるかを返します。このindexメソッドを使い、elmのi番目の値のk_list中での順番が、k_listi+1番目のそれより小さい場合には、増加写像にならないのでbreakします。このため3.ではiは0からelmの長さ-1までループさせます。

7.　forループに対してbreakされないで抜けると、else節以下の処理をします。このことにより、増加写像として残った場合のみ順列の要素が組み合わせとしてarrayに追加されます。

計算の結果10件に絞られ、順番もk_listと同じ並び順になりました。

組み合わせを生成する関数

3では順列のリストから絞り込む方法で組み合わせを生成しましたが、順列の個数はnが大きくなると爆発的に増えてしまいマシンに負荷がかかります。このため、重複順列を生成するperm_unristricted_func関数に増加写像の処理を組み込むことで組み合わせを生成する関数を作成します。

組み合わせの単射なので関数名はcomb_injective_func関数とし、これまでと同じように、引数は箱の色のリストk_listとボールの個数nとします。重複順列では1つ目に2:赤を選んでも2つ目は0:青から順次選ぶ必要がありました。一方、組み合わせは増加関数であることから、2つ目は3:紫のから選べばよいことになります。そこで、この3:紫に当たる番号を変数startでコントロールします。

組合せを生成する関数

def comb_injective_func(k_list, n):
array = [()]
for _ in range(n):
temp = array
array = []
for elm in temp:
if elm == ():
start = 0
else:
start = k_list.index(elm[-1]) + 1
for item in range(start, len(k_list)):
array.append(elm+(k_list[item],))
return array
k_list = ['青', '赤', '緑', '黄', '紫']
n = 3
comb_injective_list = comb_injective_func(k_list, n )
print('comb_injective_func(5, 3) = ',len(comb_injective_list))
if itertools_comb_list == comb_from_perm_list == comb_injective_list:
print('itertools,from permutation, comb_injective_func -- > equal ')

comb_injective_func(5, 3) =  10
itertools,from permutation, comb_injective_func -- > equal

3.　選ぶ色の数nが埋まるまでループさせます。

8.　変数start組み合わせの次の要素を選ぶときに、k_listのどのindeｘから選べばよいかを示します。初めのボールは0:青からが候補になるのでstartを0に設定します。2つ目以降のボールを入れる箱を選ぶときは、前に選んだ色番号の次からが候補になりあます。

10. k_list.index(elm[-1])は最後に選んだk_indexでの順番が代入されているので、この番号+1をstartに代入します。

11. startからk_list最後の要素まで色番号を順次選び、タプルとして追加した新しい要素をarrayに追加します。

12. 全ての繰り返しが終わった後、最終的に生成された組み合わせを戻り値として返します。

18. 作成した組み合わせを、リストcomb_injective_listに代入します。

20. Pythonでは3つのリストをつなげて、それぞれが等しいかを判断することができます。itertools、順列から選んだ組み合わせ、及びここで作成した組み合わせを比較し、全てが等しければ、その旨を表示します。

インデックスの考え方が少し面倒ですが、重複順列のプログラムを少し修正するだけで組み合わせを生成する関数を作成することができました。

いったん順列を作成してから絞り込むと、情報量が膨れ上がってしまいますが、comb_injective_funcでは、作成段階で絞り込めるので効率的であると考えられます。