PHPで組み合わせを生成する -再帰呼び出し-

(1/1)

組み合わせの生成とは

一般に、異なる n 個のものから異なる r 個のものを取り出す組み合わせの数は  mimetex  で求めることができる。
たとえば、4種類の“おはじき”A, B, C, D から 3 個を取り出す組み合わせの数は  mimetex  通りである。

ここまでは中学生の数学のレベルである。
では、実際にどのような組み合わせが出来るか?――前述の“おはじき”の例では数のような 4種類の組み合わせが出来る。
組み合わせの生成
このような組み合わせを生成するための公式は存在しない。力任せに計算する必要があるが、こうした力任せの問題にはコンピュータが力を発揮する。

そこで今回は、異なる n 個のものから異なる r 個のものを取り出す組み合わせを生成するプログラムを作ってみることにする。

サンプル・プログラム

組み合わせの生成

組み合わせを求めるのはユーザー関数 combine である。

combine自身から combine を呼び出している。
このように自分自身を呼び出す方法を再帰呼び出し(recursive call)という。

0050: /**
0051:  * 組み合わせを求める
0052:  * @param string $name 変数名
0053:  * @return string 変数の内容/変数が存在しない場合は空文字列を返す
0054: */
0055: function combine($k) {
0056:     global $g_t$g_r$g_n$g_out$g_count;
0057:     if ($k == $g_r) {
0058:         $g_count++;
0059:         $g_out[$g_count][0] = NULL;
0060:         for ($i = 1; $i <= $g_r$i++) {
0061:             array_push($g_out[$g_count]$g_t[$i] - 1);
0062:         }
0063:     } else {
0064:         $w = $g_t[$k + 1];
0065:         for ($i = $k + 1; $i <= $g_n$i++) {
0066:             $g_t[$k + 1] = $g_t[$i];
0067:             $g_t[$i] = $w;
0068:             if ($g_t[$k] < $g_t[$k + 1])  combine($k + 1);
0069:             $g_t[$i] = $g_t[$k + 1];
0070:         }
0071:         $g_t[$k + 1] = $w;
0072:     }
0073: }

(この項おわり)
header