重複組み合わせを自然数に対応付けるアルゴリズム
ちょっと数学を知っておられる方なら、n個の玉からr個を重複を許して取る組み合わせの場合の数(重複組み合わせ)はnHr=(n+r-1)Cr通りというのは周知のことかと思います。
以下、n個の玉からr個を重複を許して取る組み合わせと等価の問題、Σ_(i=1)^(n)x_i=r、を満たす0以上整数の組(x_1,x_2,…,x_n)を求める問題に置き換えて話をします。
その重複組み合わせについて、場合の数は公式から導き出されるのですが、ある事情により、その(n+r-1)Cr通りの(x_1,x_2,…,x_n)の組に対して、自然数と1対1対応させるアルゴリズムが必要になりました。
例えば、n=3,r=2の場合、問題は、
x_1+x_2+x_3=2を満たす0以上整数の組(x_1,x_2,x_3)を求める問題で、場合の数は(3+2-1)C2=4C2=6通りです。
列挙すると、
(x_1,x_2,x_3)=
{(0,0,2),
(0,1,1),
(1,0,1),
(0,2,0),
(1,1,0),
(2,0,0)}
の6つを要素に持つ集合ですが、これを次のように変換するアルゴリズム(関数)を作るのが今回の目的です。
(0,0,2)→1
(0,1,1)→2
(1,0,1)→3
(0,2,0)→4
(1,1,0)→5
(2,0,0)→6
nやrが小さくて6通り程度なら手作業でやった方が早いですが、ちょっとnやrが大きくなると場合の数が一気に大きくなって大変です。(実際に必要だったのはn=6,r=5で計252通り)
よくありそうな問題だと思って、いろいろ調べまわったのですが、ネット上では見つからなかったので、しょうがなく自分で実装することにしました。こんな感じのコードです。(言語はC#)
public int combination(int n,int k)
{
int output = 1;
for (int i = 0; i < k; i++)
{
output *= (n-i);
}
for (int i = 1; i <= k; i++)
{
output /= (i+1);
}
return output;
}
public int kumiawasesizensutaiou(int[] motohairetu,int nokori,int nokorisum)
{
//min-->>1,max-->>_{nokori+nokorisum-1}C_{nokorisum}
int output = 0;
switch (nokori)
{
case 0:
output = 1;
break;
case 1:
output = 1;
break;
default:
for (int i = nokorisum; i > nokorisum - motohairetu[nokori-1]; i--)
{
output += combination(nokori+i-2, nokori-2);
}
output += kumiawasesizensutaiou(motohairetu, nokori - 1, nokorisum - motohairetu[nokori-1]);
break;
}
return output;
}
1個目のcombination関数はただのnCkを求めるだけの関数です。(あまりにもnがでかいとnの階乗を先に計算してバーストしかねないが、今回はn=6程度なので、まぁこれでもよかろうと。)
本体はkumiawasesizensutaiou関数です。引数として、要素数nokori個を持つ、要素の和がnokorisumである配列motohairetuと、先ほどの数式でnにあたるint型nokori変数と、先ほどの数式でrにあたるnokorisum変数を持ち、motohairetu配列と1対1対応する自然数を返す関数になります。
計算は再帰関数(数学的帰納法的なやつ)を使います。
nokoriが1であれば、組み合わせは1通りなので、1を返します。
nokoriが2以上であれば、motohairetuのnokori番目の要素の値で場合分けします。
キーになる公式として、
(n+r-1)Cr=(n+r-1)C(n-1)=(n+r-2)C(n-2)+(n+r-3)C(n-2)+…+(n-2)C(n-2)
というものがあります。
motohairetuのnokori番目の要素が0の場合、(x_1,x_2,…,x_n)の組み合わせ数は(n+r-2)C(n-2)通り、
motohairetuのnokori番目の要素が1の場合、(x_1,x_2,…,x_n)の組み合わせ数は(n+r-3)C(n-2)通り、…
motohairetuのnokori番目の要素がrの場合、(x_1,x_2,…,x_n)の組み合わせ数は(n-2)C(n-2)=1通り、
という場合分けです。
motohairetuのnokori番目の要素がkの場合、対応する自然数は0~k-1のケースの場合の数、(n+r-2)C(n-2)+…+(n+k-3)C(n-2)までを足した後、見る要素を1個減らして、(nokori-1)個の玉から(r-k)個を重複を許して取る組み合わせを自然数対応させたものをプラスするという再帰計算です。
説明へたくそであれですけど、こんな感じの思考でアルゴリズムを組んでおります。あんまりないかもしれないが、もし参考になることがあったら使ってみてください。
この記事が気に入ったらサポートをしてみませんか?