組み合わせの求め方

組み合わせとは

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

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

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

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

abc	abd	abe	acd	ace
ade	bcd	bce	bde	cde

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

function getCombinationTable(n:uint,m:uint):Array{ var keta:int; var c_table:Array=new Array(); var Kumi:Array=new Array(); keta=0; Kurikaesi(m,0,n-1); return c_table; function Kurikaesi(cn:int, sn:int, en:int){//選ぶ数、はじめの数、最後の数 keta++; for(var BA:int=sn; BA<=en-cn+keta; BA++){ var le:int=c_table.length; Kumi.push(BA); if(cn==keta){ c_table[le]=new Array; for(var BB:int=0; BB<Kumi.length; BB++){ c_table[le].push(Kumi[BB]); } }else{ Kurikaesi(cn,BA+1,en); } Kumi.splice(-1); } keta--; } }

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