組み合わせ　Nラベルなし、Kあり　単射

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

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

順列と組み合わせ

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

Example 2.1

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

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

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

Figure 2.1　写像を使って順列と組み合わせを比べる^p90120_combination_map.png

(2)の組み合わせの個数は、60個の順列を選ばれた３つの箱の順列3!=6で割った10通りになります。この組み合わせは${}_kC_n$で計算することができます。

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

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

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

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

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

増加関数の考え方

青、赤、緑の3色のボールから色を選び、色の組み合わせを生成するには、まず各色に番号を振り（例：0=青, 1=黄, 2=赤, 3=紫, 4=緑…）、取り出すボールの順序を$x_0,x_1,x_2,\dots,x_n$とします。ボール自体には区別がないように見えますが、ここでの「区別」とは出席番号のような恒久的なラベルではなく、取り出した順番を示す便宜的なものと考えます。

順番に取り出す際、もし最初に選んだ$x_0$が色番号0（青）であるとすると、次の$x_1$は番号0以下（青）ではなく番号1以上（黄以降）から、同様に$x_2$は選んだ$x_1$の番号よりも大きい番号から選びます。このルールにより、取り出す順番が進むにつれて色番号は非減少（厳密には昇順）になります。

Figure 2.2 増加写像の考え方を使い組み合わせを生成\p90120_combination_index.png

例えば、0:青, 2:赤, 4:緑を選んだ場合、2:赤, 4:緑, 0:青のような別の順列は生成されず、色の組み合わせ{青, 赤, 緑}が1通りとして得られます。

このように、取り出す要素の番号が昇順となる写像を「増加写像（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つを併記します。

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

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

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

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

Code 2.1　順列を生成し、個数を表示する

  1. n = 3
  2. k_list = ['青', '赤', '緑', '黄', '紫']
  3. perm_injective_list = generate_injective_perm(k_list, n)
  4. print(
  5. f'generate_injective_perm({len(k_list)}, {n})) ='
  6. f'{len(perm_injective_list)}'
  7. )
generate_injective_perm(5, 3)) =60

3.　 generate_injective_permはあらかじめ実行しておいてください。

生成した順列を組み合わせ変換する関数を作成します。

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

  1. def filter_increasing_map(sequence, k_list = None, strict=True, reverse=False):
  2. filtered_list = []
  3. for elm in sequence:
  4. for i in range(len(elm) - 1):
  5. if strict == True and elm[i] == elm[i + 1] :
  6. break
  7. if k_list is None:
  8. elm_cur = elm[i]
  9. elm_next = elm[i + 1]
  10. if elm_cur < elm_next if reverse else elm_cur > elm_next:
  11. break
  12. else:
  13. idx_cur = k_list.index(elm[i])
  14. idx_next = k_list.index(elm[i + 1])
  15. if idx_cur < idx_next if reverse else idx_cur > idx_next:
  16. break
  17. else:
  18. filtered_list.append(elm)
  19. return filtered_list
  21. origin = [('A', 'B', 'C'),
  22. ('A', 'C', 'B'),
  23. ('B', 'C', 'C'),
  24. ('C', 'B', 'B'),
  25. ('B', 'C', 'A'),
  26. ('C', 'B', 'A'),
  27. ]
  29. filter_increasing_map(origin)
[('A', 'B', 'C')]

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

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

Code 2.3　重複順列から組み合わせに絞り込む関数

  2. k_list = ['B', 'C', 'A']
  3. print('k_list なし')
  4. print('strict = True, reverse = False : ',
  5. filter_increasing_map(origin, strict = True, reverse = False))
  6. print('strict = True, reverse = True : ',
  7. filter_increasing_map(origin, strict = True, reverse = True))
  8. print('strict = False, reverse = False : ',
  9. filter_increasing_map(origin, strict = False, reverse = False))
  10. print('strict = False, reverse = True : ',
  11. filter_increasing_map(origin, strict = False, reverse = True))
  12. print('k_list B→C→A')
  13. print('strict = True, reverse = False : ',
  14. filter_increasing_map(origin, k_list,strict = True, reverse = False))
  15. print('strict = True, reverse = True : ',
  16. filter_increasing_map(origin, k_list,strict = True, reverse = True))
  17. print('strict = False, reverse = False : ',
  18. filter_increasing_map(origin, k_list, strict = False, reverse = False))
  19. print('strict = False, reverse = True : ',
  20. filter_increasing_map(origin, k_list,strict = False, reverse = True))
k_list なし
strict = True,  reverse = False :  [('A', 'B', 'C')]
strict = True,  reverse = True  :  [('C', 'B', 'A')]
strict = False, reverse = False :  [('A', 'B', 'C'), ('B', 'C', 'C')]
strict = False, reverse = True  :  [('C', 'B', 'B'), ('C', 'B', 'A')]
k_list B→C→A
strict = True,  reverse = False :  [('B', 'C', 'A')]
strict = True,  reverse = True  :  [('A', 'C', 'B')]
strict = False, reverse = False :  [('B', 'C', 'C'), ('B', 'C', 'A')]
strict = False, reverse = True  :  [('A', 'C', 'B'), ('C', 'B', 'B')]

順番もk_listと同じ並び順になりました。

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

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

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

Code 2.4　順列から増加関数により組み合わせに変換

  1. comb_from_perm_list = filter_increasing_map(perm_injective_list)
  2. print('combinations from permutation(5, 3) = ', len(comb_from_perm_list))
  3. comb_from_perm_list
combinations from permutation(5, 3) =  10
[('赤', '青', '黄'),
 ('緑', '青', '黄'),
 ('緑', '赤', '青'),
 ('緑', '赤', '黄'),
 ('紫', '青', '黄'),
 ('紫', '赤', '青'),
 ('紫', '赤', '黄'),
 ('紫', '緑', '青'),
 ('紫', '緑', '赤'),
 ('紫', '緑', '黄')]

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

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

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

Code 2.5　itertoolsモジュールを使い組み合わせを生成

  1. import itertools
  2. k_list = ['青', '赤', '緑', '黄', '紫']
  3. n = 3
  4. itertools_comb_list = list(itertools.combinations(k_list, n))
  5. print(
  6. f'itertools.combinations({n}, {len(k_list)}) = '
  7. f'{len(itertools_comb_list)}'
  8. )
  9. if comb_from_perm_list == itertools_comb_list:
  10. print(f'comb_from_perm_list == itertools_comb_list') 
itertools.combinations(5, 3) =  10
[('青', '赤', '緑'),
 ('青', '赤', '黄'),
 ('青', '赤', '紫'),
 ('青', '緑', '黄'),
 ('青', '緑', '紫'),
 ('青', '黄', '紫'),
 ('赤', '緑', '黄'),
 ('赤', '緑', '紫'),
 ('赤', '黄', '紫'),
 ('緑', '黄', '紫')]

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

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

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

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

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

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

Code 2.6　組合せを生成する関数

  1. def generate_injective_comb(k_list, n):
  2. comb_list = [()]
  3. for _ in range(n):
  4. next_comb = []
  5. for elm in comb_list:
  6. if elm == ():
  7. start = 0
  8. else:
  9. start = k_list.index(elm[-1]) + 1
  10. for item in range(start, len(k_list)):
  11. next_comb.append(elm+(k_list[item],))
  12. comb_list = next_comb
  13. return comb_list
  15. comb_injective_list = generate_injective_comb(k_list, n )
  16. print('generate_injective_comb(5, 3) = ',len(comb_injective_list))
  17. if itertools_comb_list == comb_from_perm_list == comb_injective_list:
  18. print('itertools,from permutation, generate_injective_comb -- > equal ')
comb_injective_func(5, 3) =  10
itertools,from permutation, generate_injective_comb -- > 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最後の要素まで色番号を順次選び、タプルとして追加した新しい要素をcomb_injective_listに追加します。

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

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

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

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

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

ictsr4 All Rights Reserved.