組み合わせの求め方

組み合わせを計算するとは

　組み合わせの求め方で組み合わせのパターンを求める時に左から順番に選んでいきました。ではその選び方を計算して求めていきます。つまり、何番目の組み合わせのパターンは、１番目はどれを選んで２番目はどれでということを計算していきます。

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

　まず、a,b,c,d,eという皿が横に並んでいたすると、その５つの皿に１つのケーキを置く場合どの皿の上に置くかのパターンを考えます。
　これは当然のことですが、各皿１パターンずつあります。
　次に、５つの皿に２つのケーキを置く場合です。
　これは左端をaの皿にした場合₄C₁で４通り、bの皿の場合₃C₁で３通り、cの皿の場合₂C₁で２通り、dの皿の場合₁C₁で１通りあります。
　次は、５つの皿に３つのケーキを置く場合です。
　これは左端をaの皿にした場合₄C₂で６通り、bの皿にした場合₃C₂で３通り、cの皿にした場合₂C₂で１通りあります。
　さらに、５つの皿に４つのケーキを置く場合です。
　これは左端をaの皿にした場合₄C₃で３通り、bの皿にした場合₃C₃で１通りとなります。
　最後に、５つの皿に５つのケーキを置く場合は１通りです。

　これを表にすると次のようになります。

	₅C₁	₅C₂	₅C₃	₅C₄	₅C₅
1	₄C₀
2	₃C₀	₄C₁
3	₂C₀	₃C₁	₄C₂
4	₁C₀	₂C₁	₃C₂	₄C₃
5	₀C₀	₁C₁	₂C₂	₃C₃	₄C₄

　この表の見方がわかりにくいですが、例えば５つの皿に３つのケーキの場合に左端をaにした場合は[₅C₃ - 3]左端をbにした場合は[₅C₃ - 4]と言った具合にだんだん下がっていきます。
　ここで注目したいのが、例えば５つの皿に３つのケーキの場合に左端をaにした場合は[₅C₃ - 3]ですが、実は真ん中のケーキの動きが一つ左の列の[₅C₂ - 3]から下になっているという点です。仮に真ん中をbにすると[₅C₂ - 3]の３通り、真ん中をcにすると[₅C₂ - 4]の２通り、真ん中をdにすると[₅C₂ - 2]の１通りとなっています。さらに言うと、仮に真ん中をbにした場合の右端のケーキの動きは[₅C₁ - 3]から下になっています。このように置くケーキの順番が右に行けばいくほどその動きは表では左に行くと言うことが分かります。
　ではここで組み合わせのどのように計算することが出来るでしょうか。まず、₅C₃の組み合わせを順番にすべて上げておきます。
　abc, abd, abe, acd, ace, ade, bcd, bce, bde, cdeの１０通りです。
　では８番目の組み合わせを見てみるとbceになっていますこれをどのように計算してだすことが出来るでょうか？ここで先ほどの表を使います。これは先ほどの表を計算したものです。

	₅C₁	₅C₂	₅C₃	₅C₄	₅C₅
1	1
2	1	4
3	1	3	6
4	1	2	3	4
5	1	1	1	1	1

　まず８番目は左端のケーキはどの皿の上に乗っているかを考えます。aの皿の上では[₅C₃ - 3]で６通りです。bの皿の上は[₅C₃ - 4]で３通りになり合計９通りになります。ですから左端はbです。次に真ん中のケーキはどの皿の上でしょうか。真ん中のケーキは左端がbになってからはcの皿の上で[₅C₂ - 4]で２通りあることになり合計で８通りになります。それで、真ん中はcです。最後に右端は真ん中がcになってから、dの皿が[₅C₁ - 4]で１通りの合計７通り、eの皿が[₅C₁ - 5]で１通りの合計８通りとなり、右端はeの皿の上だと言うことが分かります。
　このように８番目の組み合わせを知りたい場合は表を用いて、３（ケーキの数）番目の列の上から順に数を足していき合計が８以上になったらその数は足さずに左に行くようにし、左端の列で合計が８になるまで続けます。そしてその動きをスタートから順にa,b,c,d,eと数えていくと、₅C₃の列はbまであり、₅C₂の列はcまであり、₅C₁の列はeまであると言うことが分かります。それで、それぞれの文字を取ったb,c,eが８番目の組み合わせとなります。

	₅C₁	₅C₂	₅C₃	₅C₄	₅C₅
1
2
3			a
4	d	c	b
5	e

組み合わせを求めるコード。elementに組み合わせの要素を入れ、表を作ってから組み合わせを求めてください。

var table:Array;
var elements:Array;

//表を作る
function set maxNumber(n:uint):void{
	n++;
	table=new Array();
	table[0]=new Array();
	for(var AA:int=0;AA<n;AA++){
		table[0][AA]=1;
	}
	for(AA=1;AA<=n;AA++){
		table[AA]=new Array();
		var sum:Number=0;
		for(var AB:int=0; AB<n-AA; AB++){
			sum+=table[AA-1][AB];
			table[AA][AB]=sum;
		}
	}
}

//組み合わせを求める
function getCombination(max:uint,c:uint,index:uint):Array{
	if(total(max,c)<index){
		return null;
	}else{
		var sum:Number=0;
		var arr:Array=new Array();
		var x:int=c-1;
		var y:int=max-c+1;
		while(x>=0){
			if(sum+table[x][y-1]>index){
				arr.push(elements[max-y-x]);
				x--;
			}else{
				y--;
				sum+=table[x][y];
			}
		}
		if(y<0){
			return null;
		}else{
			return arr;
		}
	}
}

Combinationクラス

組み合わせの求め方

組み合わせを計算するとは

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

組み合わせ

スポンサードリンク

Web検索