FC2ブログ

組み合わせの数え上げ

こんばんは
いつの間にか新学期が始まっていました。
今年で大学生活も4年目に突入です。

最近は研究室に配属されて、ゼミやら発表やらで忙しくしています。

今回は研究で組み合わせの列挙が必要になって、そのときにまあまあ効率のいい再帰アルゴリズムを思いついたので紹介します。

そもそも組み合わせとは何ぞ?という人のために少し解説します。
組み合わせとは、例えば
4人の中から2人を選ぶとき、人をa,b,c,dとおくと選び方は
{(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)}
になります。
この選び方を組み合わせと言います。

一般的に組み合わせ(Combination)はn個の中からm個を選ぶときの選び方です。
ここで注意が必要なのは似たようなもので順列(Permutation)というのがありますが、これは選び方だけではなく並べ方も考慮に入れるところが違います(実際に私もよく覚え違いをしてました...)。

では、早速アルゴリズムの説明です。
n個の中からm個を選ぶときの選び方の数は一般に「nCm」と書きますが、これは次のように変形出来ます。

nCm=(n-1)Cm+(n-1)C(m-1)

これは具体的にどういうことかというと、n個の物を一列に並べていたとすると
(n-1)Cmは最初の一つは選ばずに残りのn-1個の中からm個を選ぶ組み合わせ
(n-1)C(m-1)は最初の一つを選び、残りのn-1個の中からm-1個を選ぶ組み合わせ
になります。
こう考えると感覚的にはこの等式が成り立つように思えます。実際に
nCm=n!/(n-m)!m!
であることから、この等式が成り立つことは示せます(ここではそれは省略します)。

ここで注目すべきことは、
(1)n=mのときnCm=1
(2)m=1のときnCm=n
となるところです。
どういうことかというと、上の式変形を再帰的に適用していくとこの二つの場合に帰着するんです。
結局(1)のときは残りのn個の物すべてを選ぶことで、(2)は残りのn個のどれか一つを選ぶことに対応出来ます。

データ構造としては、長さn個の配列を用意し、n個の物を一列に並べたと考えて選ぶときは1選ばないときは0に対応づけます。

ここまで書いたことをC言語で実装すると以下のようになります


#include <stdio.h>
#include <stdlib.h>

void C(int,int,int);
void init();
void print();

int *E;
const int N = 4;
const int M = 2;

int main(int argc, const char * argv[])
{
E = (int *)malloc(sizeof(int)*N);
init();
C(N,M,0);
return 0;
}

void C(int n,int m,int i)
{
*(E+i)=1;
if(m == 1) //(2)のとき
print();
else
C(n-1,m-1,i+1); //(n-1)C(m-1)

*(E+i)=0;
if(m != n) //(1)以外のとき。残りn個のうち先頭を取らない選びかた
C(n-1,m,i+1); //(n-1)Cm
}

void init()
{
int i = 0;
while(i < N)
{
*(E+i) = 0;
i++;
}
}

void print()
{
int i = 0;
while(i < N)
{
printf("%d ",*(E+i));
i++;
}
printf("\n");
}


我ながら無駄のないプログラムを書けたと思います。
その分、関数Cが少し難解になってしまいましたが、ちょっと考えれば分かるはずです。
ちなみにこれを実行すると
a b c d
1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 1
0 0 1 1
となり、最初に述べた4人の中から2人を選ぶときの例に対応しています。

参考になるか分かりませんがご自由にお使いください。
スポンサーサイト



コメント