組み合わせの求め方

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

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

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

 まず、a,b,c,d,eという皿が横に並んでいたすると、その5つの皿に1つのケーキを置く場合どの皿の上に置くかのパターンを考えます。
 これは当然のことですが、各皿1パターンずつあります。
 次に、5つの皿に2つのケーキを置く場合です。
 これは左端をaの皿にした場合4C1で4通り、bの皿の場合3C1で3通り、cの皿の場合2C1で2通り、dの皿の場合1C1で1通りあります。
 次は、5つの皿に3つのケーキを置く場合です。
 これは左端をaの皿にした場合4C2で6通り、bの皿にした場合3C2で3通り、cの皿にした場合2C2で1通りあります。
 さらに、5つの皿に4つのケーキを置く場合です。
 これは左端をaの皿にした場合4C3で3通り、bの皿にした場合3C3で1通りとなります。
 最後に、5つの皿に5つのケーキを置く場合は1通りです。

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

5C15C25C35C45C5
14C0
23C04C1
32C03C14C2
41C02C13C24C3
50C01C12C23C34C4

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

5C15C25C35C45C5
11
214
3136
41234
511111

 まず8番目は左端のケーキはどの皿の上に乗っているかを考えます。aの皿の上では[5C3 - 3]で6通りです。bの皿の上は[5C3 - 4]で3通りになり合計9通りになります。ですから左端はbです。次に真ん中のケーキはどの皿の上でしょうか。真ん中のケーキは左端がbになってからはcの皿の上で[5C2 - 4]で2通りあることになり合計で8通りになります。それで、真ん中はcです。最後に右端は真ん中がcになってから、dの皿が[5C1 - 4]で1通りの合計7通り、eの皿が[5C1 - 5]で1通りの合計8通りとなり、右端はeの皿の上だと言うことが分かります。
 このように8番目の組み合わせを知りたい場合は表を用いて、3(ケーキの数)番目の列の上から順に数を足していき合計が8以上になったらその数は足さずに左に行くようにし、左端の列で合計が8になるまで続けます。そしてその動きをスタートから順にa,b,c,d,eと数えていくと、5C3の列はbまであり、5C2の列はcまであり、5C1の列はeまであると言うことが分かります。それで、それぞれの文字を取ったb,c,eが8番目の組み合わせとなります。

5C15C25C35C45C5
1
2
3a
4dcb
5e

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

Combinationクラス