組み合わせの求め方

組み合わせとは

 組み合わせとは、n個ある物の中からm個ぶときに取り出した順番を気にせずに並べたものです。

組み合わせのパターンを求める

 組み合わせとは言い換えると、例えばa,b,c,d,eという皿が横に並んでいたすると、その5つの皿に3つのケーキを置く場合どの皿の上に置くかのパターンです。
 そのように考えると3つ並べた時の左端は右にケーキが2つあるはずなので必ずa,b,cの内のどれかになります。 仮にbを選んだとします。次に左から2番目(真ん中)のケーキは左端のケーキよりは右になければなりませんし、右にはケーキが1つくるはずなので必ず1つは空けなければなりません。で すからこの場合c,dの内のどれかということになります。ここではcを選ぶと仮定します。最後に右端のケーキは2番目のケーキよりも右になければなりません。それで右端はd,eの内のどれかになります。

 これらの点を考えると、組み合わせのすべてのパターンを求めるためには、左から順にケーキを置く皿を選んでいき、 それぞれのケーキに置ける範囲があると言うこと、置ける範囲は左にあるケーキと後何個ケーキを置かなければならないかによって変化することが分かります。 この方法で全部のパターンを求めるとこうなります。

abcabdabeacdace
adebcdbcebdecde

 これらの点をふまえ、nCmの組み合わせのパターンをすべて求めるコードは次のようになります。

 しかしこの方法で行うと、問題があります。例えば25C12などの組み合わせを求めると5,200,300通りあります。 この組み合わせをすべてを変数に入れるとかなりメモリを消費します(これほどの計算をすること自体が間違っているのかもしれませんが…)。 ですからすべての組み合わせを記憶してなくても、順番に組み合わせを計算して選ぶことが出来るようにしたいと思います。