HOME Open Source
ここでは、順列と組合せのアルゴリズムを実装したサンプルを公開しています。組合せとは、『赤、青、黄、緑のボールが1つずつ合計4個あったとします。この中から、2個を取り出す場合の、組合せは、何通りありますか?』といったやつです。取り出す順番を問わないのが、組合せ(赤青、青赤は同じ)で、順番により異なる組合せとみなすのが、順列(赤青、青赤は異なる組合せ)です。
私が自作している麻雀ゲームで、この組合せ(手牌、捨牌)の考え方が必要な場面があり、そのとき初めて作成したのですが、これが中々、苦労したので、今回、これを流用してサンプルとして、公開することにしました。
具体的には、商品マスタに含まれる商品を、セット販売した場合にどのような組合せが考えられるかという内容のものとなっています。
ソースコードは、Microsoft社の製品 エクセル向けに書いたものなので、利用するには、ご使用のコンピュータに、エクセルがインストールされていることが、必須条件です。
以下は、サンプル画面です。
赤(idx=0)、青(1)、黄(2)、緑(3)の4個のボールがあったとします。例として、この中から3個を取り出した場合の順列の組合せを説明します。
数学的に表記すると、順列の組合せの個数は、nPr と表現できるが、これは、n個の中からr個取り出す順列と解釈できます。
今回の例の場合、順列の総数は、4P3で算出できるが、私がプログラムで実装したアルゴリズムは、n進数r桁の数値をつくっていくという考え方で、以下のようになっています。
{ 赤, 青 , 黄, 緑 } の4個の中から3個取り出す場合、000から始まる、4進数3桁の値をつくり、各桁の値で、重複するものが存在する場合は除外します。数値は、idxの並びと思ってください。
以下の内容に則しながら、組合せのアルゴリズムについて説明します。
赤(idx=0)、青(1)、黄(2)、緑(3)、白(4)の5個のボールがあったとします。この中から3個を取り出した場合の、組合せを考えていきましょう。
数学的に表記すると、組合せの個数は、nCr と表現できるが、これは、n個の中からr個取り出す組合せと解釈できます。
今回の例の場合、組合せの総数は、5C3で算出できるが、私がプログラムで実装したアルゴリズムは以下のようになっています。
{ 赤, 青 , 黄, 緑 , 白 } の5個の中から3個取り出す場合、順列と同等で、基本的には、5進数3桁を作っていくのですが、組合せの場合は、順序を考慮しないので、n進数の各桁のとりうる範囲が決まってきます。
5C3=10通り。
012で始まる値を、1ずつインクリメントし、5進数3桁をつくり、桁のとりうる範囲を考慮しながら、繰り上げ処理時に、次のとりうる値まで、値を一気に読みとばすというものです。値が014となったときに、1インクリメントすると、次は、020なのですが、023にしてしまうというのものです。さらにインクリメントを続けながら、024になって、1インクリメントしたときに、本来は、030なのですが、034にしてしまいます。数値はidxの並びと思ってください。
少し分かりにくいかもしれませんが、ソースコードと比較しながら、理解してみてください。
作者は、本ソフトウェアの使用または使用不能から生じるコンピュータの故障、情報の消失、その他あらゆる直接的及び間接的被害に関して一切の責任を負いません。
ご使用にあたり、改善の要望、不具合の発生等ありましたら、画面下のアドレスまで、ご連絡頂きますよう、宜しくお願いいたします。ご面倒、ご不便をお掛けしますが、宜しくお願いいたします。
