重複組み合わせ　Nラベルなし、Kラベルあり　一般写像

写像から見た重複組み合わせ

組み合わせは集合Kから1つしか選ぶことができませんが、重複組み合わせでは重複して選ぶことができます。このため、組み合わせに比べ複雑になりますが、写像と増加関数の考え方を使うと簡単に整理することができます。

重複組み合わせの考え方

重複組み合わせの考え方

まずは、単射の組み合わせとの違いを見るため、次の問題を考えます。

Example 2.1

区別の無い5つのボールを、青、赤、緑の色がついた3つの箱に入れるとするときの場合の数を計算してください。なお、各箱には重複してボールを入れることができ、空の箱があってもよいものとします。

写像にすると、左の図のようになり、集合Kの要素は空白も複数の要素から対応付けられるので、組み合わせの単射に対し制約なし(unrestricted)のパターンになります。また、増加関数の考え方を使うため、集合Kの色には色番号を付けます。

Figure 2.3　写像からみた組み合わせと重複組み合わせ\p90120_comb_compare.png

Code 2.7　重複順列からフィルター

  1. k_list = ['青', '赤', '緑']
  2. n = 5
  3. unrestricted_perm_list = generete_unrestricted_perm(k_list, n)
  4. print(
  5. 'generete_unrestricted_perm(5, 3) =',
  6. len(unrestricted_perm_list)
  7. )
generete_unrestricted_perm(5, 3) = 243

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

itertoolモジュールのcombinations_with_replacement関数により、重複組み合わせを生成することができます。引数は集合Kのリストと、集合Nの個数を渡し、重複組み合わせの一覧がジェネレータとして返ります。

Code 2.8　itertoolsモジュールを使い重複組み合わせを生成する

  1. itertools_unrestrict_list = list(itertools.combinations_with_replacement(k_list, n))
  2. print('itertools.combinations_with_replacement(3, 5)= ', len(itertools_unrestrict_list))
  3. itertools_unrestrict_list
itertools.combinations_with_replacement(3, 5)=  21
[('青', '青', '青', '青', '青'),
 ('青', '青', '青', '青', '赤'),
 ('青', '青', '青', '青', '緑'),
 ('青', '青', '青', '赤', '赤'),
 ('青', '青', '青', '赤', '緑'),
 ('青', '青', '青', '緑', '緑'),
 ('青', '青', '赤', '赤', '赤'),
 ('青', '青', '赤', '赤', '緑'),
 ('青', '青', '赤', '緑', '緑'),
 ('青', '青', '緑', '緑', '緑'),
 ('青', '赤', '赤', '赤', '赤'),
 ('青', '赤', '赤', '赤', '緑'),
 ('青', '赤', '赤', '緑', '緑'),
 ('青', '赤', '緑', '緑', '緑'),
 ('青', '緑', '緑', '緑', '緑'),
 ('赤', '赤', '赤', '赤', '赤'),
 ('赤', '赤', '赤', '赤', '緑'),
 ('赤', '赤', '赤', '緑', '緑'),
 ('赤', '赤', '緑', '緑', '緑'),
 ('赤', '緑', '緑', '緑', '緑'),
 ('緑', '緑', '緑', '緑', '緑')]

1　重複組み合わせはitertoolsモジュールのcombinations_with_replacement関数で生成することができます。

一部省略していますが、全部で21通りの組み合わせが考えられます。

「しきり」による考え方

「しきり」による重複組み合わせの計算

重複組み合わせを写像と、一般的に使われる分割の「しきり」とボールであらわす方法で考えます。この方法を使い、重複組み合わせのいくつかのパターンで整理します。

①典型的な重複組み合わせ

図の右側のように、5個の区別の無いボールを並べ、その間に青と赤を分ける「しきり」と赤と緑を分ける「しきり」を入れます。このケースは青2個、赤2個、緑1個とまっとうな組み合わせになります。

Figure 2.4　典型的な重複組み合わせ\p90120_duplicate_combination1.png

②端ではない色が選ばれない場合

制約なしの場合、青3つ緑2つが選ばれ、真ん中の赤が選ばれないようなケースも認められます。この場合、青と赤を分ける「しきり」と、赤と緑を分ける「しきり」が青と緑の間に並びます。

Figure 2.5　端ではない要素が選ばれないケース\p90120_duplicate_combination2.png

③端の色が選ばれない場合

右端の色は緑になりますが、この場合図表6のように一番右側に赤と青の「しきり」が入ります。

Figure 2.6　端の要素が選ばれないケース\p90120_duplicate_combination3.png

3つのケースを見ると、「しきり」2つとボール5つを7つのマスに並べる際の組み合わせを計算することで重複組み合わせの個数を計算することができます。

一般化すると、ボールの数nと「しきり」の数(k-1)を足したn+k-1個の中からボールn個を選ぶことになります。また「しきり」の方に注目すれば、仕切りk-1個を選ぶことと同じ意味になります。このような区別なないn個のボールをk色の箱に重複を許して選ぶ重複組み合わせの個数を${}_k H_n$で表し、計算式は次の通りです。

増加写像としての重複組み合わせ

増加写像の考え方

重複組み合わせを増加組み合わせの数式で表すと、組合せとは異なり前と同じ色を選んでもよいので、図の①のように$0\leqq x_0\leqq x_1 \leqq x_2\leqq x_3\leqq x_4\leqq 2$となります。ところで$x_i$は整数なので$x_i\leqq x_{i+1}\leftrightarrows x_i\lt x_{i+1}+1$となり、$\ 0\leqq x_0\lt x_1+1\lt x_2+2\lt x_3+3\lt x_4+4 \leqq2+4=6$と書き換えることができます。ここで、$y_i=x_i+1 (i=0,1,2,\cdots ,k-1)$を代入すると$\ 0\leqq y_0\lt y_1\lt y_2\lt y_3\lt y_4\leqq 6$となり図の下のようになります。

Figure 2.7　重複組み合わせと増加写像\p90120_duplicate_monotonic.png

①の$x_4$の最大値は2なので、$y_4$の最大値は6となるところに注意が必要です。次に1始まりの方法を考えます。

$1 \leqq x_1\leqq x_2\leqq x_3\leqq x_4\leqq x_5\leqq 3$

$\leftrightarrows 1\leqq x_1\lt x_2+1\lt x_3+2\lt x_4+3\lt x_5+4\leqq 3+4=7$となります。$y_i=x_i+i-1 (i=1,2,3\cdots ,k)$を代入すると$1\leqq y_1\lt y_2\lt y_3\lt y_4\lt y_5\leqq =7$となり、${}_7C_5$となります。

結果的に①の全ての組み合わせを集合1、②の全ての組み合わせを集合２とすると、集合１から集合２の各項に0,1,2,3,4を足した写像であり、逆に集合2は集合2から集合Ⅰへの対応は各項から0,1,2,3,4を引いた写像となり、2つの集合は逆写像がとなるので全単射となり個数が等しくなります。

ただし、コンピュータの世界では添え字は0から始まりますが、一般的には1から始まるので、それに倣うと次のように表現します。

$1\leqq y_1\lt y_2\lt y_3\lt y_4\lt y_5\leqq 3+4=7$

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

写像の考え方によると、重複組み合わせのような対応を広義の増加写像といい、組み合わせを狭義の増加写像といいます。組み合わせは単射の対応であったように、狭義の増加写像であることと単射は同じことをいいます。

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

Code 2.9　重複組み合わせの個数を計算

  1. def H(k, n):
  2. return C(n+k-1, n)
  4. print('H(3 ,5)=', H(3, 5))
H(3 ,5)= 21

2.　あらかじめC関数を実行しておく必要があります。

重複組み合わせをイメージするのには少し努力が必要ですが、その一覧を生成するプログラムは組み合わせの生成のプログラムを広義の単調増加関数にするため、1つだけ変更を加えるだけです。

Code 2.10　制約なしの写像としての重複組み合わせを生成する

  1. def generate_unrestrict_comb(k_list, n):
  2. comb_list = [()]
  3. for cnt in range(n):
  4. temp = comb_list
  5. comb_list = []
  6. for elm in temp:
  7. if elm == ():
  8. start = 0
  9. else:
  10. start = k_list.index(elm[-1]) # +
  11. for item in range(start, len(k_list)):
  12. comb_list.append(elm + (k_list[item],))
  13. return comb_list
  15. k_list = ['青', '赤', '緑']
  16. n = 5
  17. comb_unrestrict_list = generate_unrestrict_comb(k_list, n )
  18. print('injective=', len(comb_unrestrict_list), 'H関数', H(len(k_list), n))
  19. comb_unrestrict_list == comb_unrestrict_list injective= 21 H関数 21.0
[('青', '青', '青', '青', '青'),
 ('青', '青', '青', '青', '赤'),
 ('青', '青', '青', '青', '緑'),
 ('青', '青', '青', '赤', '赤'),
 ('青', '青', '青', '赤', '緑'),
 ('青', '青', '青', '緑', '緑'),
 ('青', '青', '赤', '赤', '赤'),
 ('青', '青', '赤', '赤', '緑'),
 ('青', '青', '赤', '緑', '緑'),
 ('青', '青', '緑', '緑', '緑'),
 ('青', '赤', '赤', '赤', '赤'),
 ('青', '赤', '赤', '赤', '緑'),
 ('青', '赤', '赤', '緑', '緑'),
 ('青', '赤', '緑', '緑', '緑'),
 ('青', '緑', '緑', '緑', '緑'),
 ('赤', '赤', '赤', '赤', '赤'),
 ('赤', '赤', '赤', '赤', '緑'),
 ('赤', '赤', '赤', '緑', '緑'),
 ('赤', '赤', '緑', '緑', '緑'),
 ('赤', '緑', '緑', '緑', '緑'),
 ('緑', '緑', '緑', '緑', '緑')]

10.　1つの箱が選択されたのち、次の箱を選ぶときには前と同じものを選ぶことも許されます。このため、startを選ぶときにstart = k_list.index(elm[-1])として組み合わせの時の#+1を削除するだけの変更になります。

増加写像の考え方は、プログラムを作成するうえではすごい威力を発揮することがわかります。

ictsr4 All Rights Reserved.