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

組み合わせの生成とは

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

ここまでは中学生の数学のレベルである。
では、実際にどのような組み合わせが出来るか？――前述の“おはじき”の例では数のような4種類の組み合わせが出来る。

（2022年5月7日）PHP8対応，リファラ・チェック改良．コマンドラインからの実行対応（CUI版）

このような組み合わせを生成するための公式は存在しない。力任せに計算する必要があるが、こうした力任せの問題にはコンピュータが力を発揮する。

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

プログラムを実行する

サンプル・プログラムの実行例

サンプル・プログラム

ダウンロード（PHP8対応）

圧縮ファイルの内容
combines.php	サンプル・プログラム本体

ユーザー関数 isCommandLine、isButton、getParam については、「PHPでGET／POSTでフォームから値を受け取る」をご覧いただきたい。

組み合わせの生成

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

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

307: /**
308:  * 組み合わせを求める
309:  * @param   string $name 変数名
310:  * @return  string 変数の内容／変数が存在しない場合は空文字列を返す
311: */
312: function combine($k) {
313:     global $g_t, $g_r, $g_n, $g_out, $g_count;
314:     if ($k == $g_r) {
315:         $g_count++;
316:         $g_out[$g_count][0] = NULL;
317:         for ($i = 1; $i <= $g_r; $i++) {
318:             array_push($g_out[$g_count], $g_t[$i] - 1);
319:         }
320:     } else {
321:         $w = $g_t[$k + 1];
322:         for ($i = $k + 1; $i <= $g_n; $i++) {
323:             $g_t[$k + 1] = $g_t[$i];
324:             $g_t[$i] = $w;
325:             if ($g_t[$k] < $g_t[$k + 1]) combine($k + 1);
326:             $g_t[$i] = $g_t[$k + 1];
327:         }
328:         $g_t[$k + 1] = $w;
329:     }
330: }