全射の重複組み合わせ

1 全射（空きがない）の重複組み合わせの考え方

重複組み合わせは、制約なしという条件で、空になる箱を許していましたが、ここでは空になる箱を許さない全射について考えます。制約なしと全射の重複組み合わせを比較するため、次の問題を考えます。

問題3

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

重複組み合わせにはitertoolsモジュールのcombinations_with_replacement関数が用意されているのに対し、全射の重複組み合わせを生成する関数は見当たらないので、独自に作成します。

制約なしの重複組み合わせを全射にする

全射の重複組み合わせの生成

comb_unristrict_func関数を使い、重複組み合わせを生成したのち、全ての色が選ばれている組み合わせのみを抽出することにより、全射の重複組み合わせを生成します。

制約なしの重複組み合わせから全射の組み合わせを絞り込む

k_list = ['青', '赤', '緑']
n = 7
comb_unrestrict_list = comb_unrestrict_func(k_list, n)
comb_surjective_list = []
for elm in comb_unrestrict_list:
if set(k_list) == set(elm):
comb_surjective_list.append(elm)
print('unrestrict : ', len(comb_unrestrict_list), ' surjective : ', len(comb_surjective_list))
comb_surjective_list

unrestrict :  36    surjective :  15
[('青', '青', '青', '青', '青', '赤', '緑'),
 ('青', '青', '青', '青', '赤', '赤', '緑'),
 ('青', '青', '青', '青', '赤', '緑', '緑'),
 ('青', '青', '青', '赤', '赤', '赤', '緑'),
 ('青', '青', '青', '赤', '赤', '緑', '緑'),
 ('青', '青', '青', '赤', '緑', '緑', '緑'),
 ('青', '青', '赤', '赤', '赤', '赤', '緑'),
 ('青', '青', '赤', '赤', '赤', '緑', '緑'),
 ('青', '青', '赤', '赤', '緑', '緑', '緑'),
 ('青', '青', '赤', '緑', '緑', '緑', '緑'),
 ('青', '赤', '赤', '赤', '赤', '赤', '緑'),
 ('青', '赤', '赤', '赤', '赤', '緑', '緑'),
 ('青', '赤', '赤', '赤', '緑', '緑', '緑'),
 ('青', '赤', '赤', '緑', '緑', '緑', '緑'),
 ('青', '赤', '緑', '緑', '緑', '緑', '緑')]

3.　生成した重複組み合わせを、配列comb_unrestrict_listに格納します。

6.　comb_unrestrict_listの1つ1つの組み合わせをelmで取り出し集合に変換します。同様にk_listも集合に変換して比較し、等しければ全射であると判断することができます。

7.　全射の組み合わせをcomb_surjective_listに格納します。

全射の重複組み合わせを生成する関数はPythonの標準ライブラリなどには見当たりません。まず間違いないものと考えられますが、別の視点で個数を計算するなどの方法により、より確実なものにしていきます。

ボールと「しきり」の考え方で個数を計算する

ボールと「しきり」の考え方

前項のなかで制約なしの重複組み合わせを3つのパターンで整理しました。このうち全射となると①「典型的な重複組み合わせ」（図表4）のみが対象となり、②「一部の色が選ばれない」（図表5）　のように「しきり」が隣り合ったり、③「端の色が選ばれない場合」（図表6）のように「しきり」が両端に来たりするものは許されません。

そこで、ボールと「しきり」混ぜた中からボールまたは「しきり」を選ぶのではなく、図表8のように、n=7、k=3の場合、6か所のうち2か所に「しきり」を入れる組み合わせを計算することにより、全射の重複組み合わせの個数を求めることができます。もちろん、6か所のうち「しきり」が入らない４か所を選ぶ組み合わせと考えることもできます。

図の通り$\ _6 C_2=\ _6 C_4=15$通りになります。一般化するとn-1個のすき間からk-1個を選んでしきりを入れるので$\ _{n-1} C_{k-1}$となります。その結果、全射の重複組み合わせの個数は$\ _{n-1} C_{k-1}=\ _{n-1} C_{n-k}$の式で計算することができます。

整理のため、単射の組み合わせ、制約なしの重複組み合わせ、及び全射の重複組み合わせについてまとめると次のようになります。

数式2-5重複組み合わせの個数の計算

i:単射いわゆる組み合わせ

$\ _k C_n$

u:制限なしの重複組み合わせ

n個の区別のないボールをk種類の箱に重複を許して入れる場合の組み合わせ数

（0個の箱があってもOK）

$\ _k H_n = \ _{n+k-1} C_n=\ _{n+k-1} C_{k-1}$

s:全射の重複組み合わせ

n個の区別のないボールをk種類の箱に重複を許して入れる場合の組み合わせ数

（空の箱は許さない）

$\ _k H_{n-k} =\ _{n-1} C_{n-k}=\ _{n-1} C_{k-1}$

組み合わせ、重複組み合わせの個数を計算する関数

意外なことに重複組み合わせの個数を計算する関数はPythonの標準ライブラリには見当たりません。あまりに単純なのが原因かもしれませんが、作っておくと便利です。関数名もシンプルにHとし、引数はkとnの個数とし、重複組み合わせを求める場合は、オプションで制約なしの場合は”u”、全射の場合は”s”を指定します。なお、実行する際にSciPyのcomb関数を使うのでインポートしておきます。

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

def H(k, n ,option='u'):
"""
n個の要素から重複を許してk個を取り出す重複組み合わせの個数を計算
Parameters:
-----------
k : int
kの要素数
n : int
nの要素数。
option : str, optional, default='i'
組み合わせの生成方法を指定するオプション。
'u' (unrestricted):選ばれない要素を許す制約なしの重複組み合わせ
's' (surjective): 1つは選ばれる必要がある全射の重複組み合わせ
Returns:
--------
int
重複組み合わせの個数
"""
if option == 'u':
return int(comb(n + k - 1, k - 1))
if option == 's':
return int(comb(n - 1, k - 1))
print('unrestrict : ', H(3, 7, 'u'), ' surjective : ', H(3, 7, 's'))

unrestrict :  36    surjective :  15

1.　3番目の引数をoption='u'とすることで、重複組み合わせ（制約なし）をデフォルトとします。

2.　複数行にわたるコメントを入れるときは’’’ ‘’’で囲います。行単位のコメントとは異なり、通常のプログラムのコードを書くときと同じように、インデントを合わせる必要があります。ここでのコメントはdocstringといい、”? combinations_func”と入力すると表示されます。

n=7、k=3の場合、制約なしの重複組み合わせは36通りに対し、全射にすると15通りに絞られることになり、$\ _6 C_2=\ _6 C_4=15$通りと一致することを確認することができました。

あらかじめ各色を1つずつ選び全射の条件を確保する方法

全射の重複組み合わせを計算、図表のように生成する場合、図表9のようにはじめにk個の色にボールを1つずつ選んで全射である状態を確保した上で、残りボールを制約なしで重複組み合わせを計算するテクニックがあります。

制約なしなのである色が選ばれなくてもよかったのですが、全射の場合は少なくとも1つは選ぶ必要があります。そこで、とりあえずk個の色の箱にボール1つずつ計k個を入れることにより全射の条件を満たし、あとは残ったn-k個のボールは制約なしのときと同じようにボールを箱に割り振ればよいことになります。

3個のボールに対して青、赤、緑の色をそれぞれ対応させ、全射の状態であることを確保します。

残り4個のボールについて、制約なしで重複組み合わせを生成します。図表では赤が選ばれていませんが、①ですでに1つ確保されているので問題ありません。

②の個数は$\ _4 H_3 =\ _6 C_4=15$となり、全射の重複組み合わせの個数と一致します。

全射の重複組み合わせを生成する場合は、②の組み合わせに①で確保した青、赤、緑を1つ追加します。

一般化すると、全射の重複組み合わせの個数は$\ _k H_{n-k} =\ _{n-1} C_{n-k}$となり、前項の結果と一致します。

さっそく、全射の重複組み合わせを生成するプログラムを作成します。はじめにk個の全射を確保するためn-k個で制約なしの重複組み合わせを生成し、最後に各色を1個ずつ追加します。

k_listを確保して後から追加する方法で全射の重複組み合わせを生成

def comb_surjective_by_unrestrict_func(k_list, n):
array = []
for elm in comb_unrestrict_func(k_list, n - len(k_list)):
new_elm = tuple(sorted(elm + k_list, key = lambda x:k_list.index(x)))
array.append(new_elm)
return array
k_list = ('青', '赤', '緑')
n = 7
comb_surjective_by_unrestrict_list = comb_surjective_by_unrestrict_func(k_list, n)
print('comb_surjective_by_unrestrict : ', len(comb_surjective_by_unrestrict_list))

comb_surjective_by_unrestrict :  15

3.　 comb_unristrict_func 関数を使い、n個のボールからk_listにあるボールを1つずつ取り除いたn-len(k_list)個から制約なしで重複組み合わせを生成し、1つずつelmとして取り出します。

4.　あらかじめ選んだ各色の球と考えられるk_listとelmを結合すると全射の重複組み合わせになります。ただし、順番がきれいにならんでいないので、soeted関数を使い整列します。この際に、k_listをソートのキーにします。

増加関数の考え方を使う方法

全射の重複組み合わせを増加関数の数式であらわすのは簡単ではありませんが、

$a \lesssim b$ を「$b$ は $a$ に等しいか、$a$ より1だけ大きい」$a \leqq b \leqq a+1$というような記号を独自に定義すれば何とか表現することができます。

$0 = x_0\lesssim x_1\lesssim \cdots \lesssim x_{n-1} = k-1$

ここでは次の３点がポイントになります。

$x_0$は必ず0番目の要素になるので0になります。

$x_1$以降は前の要素と同じが1つ大きいという$\lesssim b$で表します。

最後の要素はk_listの最後の要素（k-1番目）と等しくなります。

増加関数を使ったプログラムを実現するために、次の工夫をします。

作成する組み合わせのはじめの要素に$k_0$の色（青）をはじめから入れておきます。

$\lesssim$記号（等しいか1つ大きい）を実現するため、1つ前の要素を読み込み、次の要素は前と同じ色からその次の色までを選ぶようにします。

最後の要素$x_{n-1}$はk_listの最後の色とするため、現在作成している要素の場所をn_index、現在選択した色がk_indexの何番目かを把握し、残りいくつかn-n_indexと残りの色が何色あるかk_k_indexを比べることにより、ここからどう頑張っても全射にならない組み合わせのものは候補から外すようにします。

増加関数の考え方を使い全射の重複組み合わせを生成する

def comb_surjective_func(n, k_list):
array = [()]
for cnt in range(n):
temp = array
array = []
for elm in temp:
if cnt == 0:
array.append((k_list[0],))
else:
start = k_list.index(elm[-1])
end = min(start + 2, len(k_list))
if cnt > 0:
for k_index in range(start, end):
if n - cnt +1 > len(k_list) - k_index :
array.append(elm + (k_list[k_index],))
return array
k_list = ['青', '赤', '緑']
n = 7
if comb_surjective_list == comb_surjective_by_unrestrict_list == comb__monotonic_list:
print('from unrestricted == surjective == monotonic')

from unrestricted == surjective == monotonic

1.　new_elmには、elmと1つずつ全射の重複組み合わせを作成します。全射であることから、1番目の要素は青(k_list[0])になるので、強制的に初期化します。

6.　読み込んだ要素をnew_elmに追加していきますが、前の色と変わったときは、初めに確保しておいた色を追加します。

11. elmに２番目以降の色が含まれていないと、その色が欠けてしまうので、追加します。選ぶ色はstartからstart+1（プログラム上は+2）までとします。最後の（n-1）番目の要素を選ぶときはstart+1にするとリストの数を超えてエラーになるのでmin関数でk_listの大きさで止めるようにします。

12. 上記③の条件を満たすため場合のみarrayに候補として追加します。

正しく計算することができました。制約なしの候補を作ってから全射の条件で絞り込むより、作成段階で条件に合わないものを切り捨てていく方が効率が良くなることが期待されます。

数式2-4全射の重複組み合わせを表す増加写像

$1 \leqq x_1 \leqq x_2 \leqq \cdots \leqq x_{n-k} \leqq k$

$ x_i\geqq 0\quad(i=1,2,\cdots,n)$

$\Leftrightarrow 1 \leqq x_1 < x_2+1 < x_3+2 < \cdots < x_{n-k}+n-k-1 \leqq k+n-k-1$

$\Leftrightarrow 1 \leqq y_1 < y_2< y_3 < \cdots < y_{n-k} \leqq n-1$

$\ _k H_{n-k} =\ _{n-1} C_{n-k}=\ _{n-1} C_{k-1}$

やはりこの場合も$\ _k H_{n-k} =\ _{n-1} C_{n-k}=\ _{n-1} C_{k-1}$と同じ式で表すことができます。

組み合わせの関数をまとめる

組み合わせおよび重複組み合わせを生成する関数をまとめる

これまで単射、制約なし、全射の組み合わせを生成する関数を作成してきました。基本的な流れはほぼ同じで、それぞれ少しずつ修正を加えることで機能を実現することができました。そこで、これらの3つの関数をまとめたcombinations_func関数を作成します。

このため、3つ目の引数はoptionとし、次に通り設定します。

'i' (injective): 組み合わせ　default

'u' (unrestricted): 重複組み合わせ

's' (surjective):全射の重複組み合わせ

なにも指定しない場合（default）

なお、このように決めごとをしても、関数を使う人にはわからないし、この関数の中では誤ったoptionを指定した場合のエラー処理も含まれていないので、docstringを追加します。

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

def combinations_func(k_list, n, option='i'):
"""
与えられたリストk_listから、n個の要素の組み合わせを生成する関数。
Parameters:
-----------
k_list : list
組み合わせを生成するための要素のリスト。
n : int
生成する組み合わせの要素数。
option : str, optional, default='i'
組み合わせの生成方法を指定するオプション。
'i' (injective): 要素が増加する順序で組み合わせを生成する（昇順組み合わせ）。
'u' (unrestricted): 要素の順序を考慮せず、同じ要素を繰り返し使用可能な組み合わせを生成する（重複組み合わせ）。
's' (surjective): 重複を許さず、全ての要素を使用した組み合わせのみを生成する（全射的組み合わせ）。
Returns:
--------
list of tuples
生成された組み合わせのリスト。各組み合わせはタプルとして表現される。
"""
array = [()]
for cnt in range(n):
temp = array
array = []
for elm in temp:
if cnt == 0:
start = 0
if option == 's':
array.append((k_list[0],))
else:
start = k_list.index(elm[-1]) + (1 if option == 'i' else 0)
end = len(k_list) if option != 's' else min(start + 2, len(k_list))
for k_index in range(start, end):
if option != 's' or (cnt > 0 and n - cnt + 1 > len(k_list) - k_index):
array.append(elm + (k_list[k_index],))
return array
k_list = ['青', '赤', '緑', '黄', '紫']
n = 3
if comb_injective_list == combinations_func(k_list, n, option='i'):
print('injective(3,7) Ok',len(comb_injective_list))
k_list = ['青', '赤', '緑']
n = 5
if comb_unrestrict_list == combinations_func(k_list, n, option='u'):
print('unristricted(3,5) Ok',len(comb_unrestrict_list))
k_list = ['青', '赤', '緑']
n = 7
if comb_surjective_list == combinations_func( k_list, n, option='s'):
print('surjective(3,7) Ok', len(comb_surjective_list))

injective(3,7) Ok 10
unristricted(3,5) Ok 21
surjective(3,7) Ok 15

31. 増加写像を使って組み合わせを生成するので、１つの項目を選んだあと次の項目をk_listの何番目から追加するのかをstartに代入します。単射である純粋増加写像の場合は前のインデックス+1、それ以外は前のインデックスにするため0になります。1 if option == 'i' else 0は三項演算子といい、条件文を1行で書くことができます。

33.　組み合わせを1つ1つ作成するために、elmに選んだ色を追加しますが、全射の場合のみ一番最後(cnt==n-1)のときだけ、全射にならない組み合わせを(len(set(new_elm)) != len(k_list)))で判断してarrayに追加しないようにします。

combinations_func関数を使い、これまで例として扱ってきたケースについて組み合わせを計算すると、結果が正しいことがわかります。