PHPで単一の配列から指定サイズのすべての組み合わせを生成する方法

PHPでは、再帰的な関数を利用することで、単一の文字セット（配列）から指定したサイズのすべての組み合わせを効率的に生成できます。ここでは、samplingという再帰関数を実装し、指定した文字数の組み合わせを出力する方法をサンプルコードとともに解説します。

サンプルコード

function sampling($chars, $size, $combinations = array()) {
    # 最初の呼び出しの場合、組み合わせの初期値として文字セットそのものを使用
    if (empty($combinations)) {
        $combinations = $chars;
    }
    # サイズが1になれば処理は完了
    if ($size == 1) {
        return $combinations;
    }
    # 新しい組み合わせを格納するための配列を初期化
    $new_combinations = array();
    # 既存の組み合わせと文字セットをループし、文字列を連結していく
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }
    # 次のイテレーションのために同じ関数を再帰的に呼び出す
    return sampling($chars, $size - 1, $new_combinations);
}
$chars = array('a', 'b', 'c');
$output = sampling($chars, 2);
var_dump($output);

実行結果

上記のコードを実行すると、次のような出力が得られます。

array(9) { [0]=> string(2) "aa" [1]=> string(2) "ab" [2]=> string(2) "ac" [3]=> string(2) "ba" [4]=> string(2) "bb" [5]=> string(2) "bc" [6]=> string(2) "ca" [7]=> string(2) "cb" [8]=> string(2) "cc" }

コードの仕組み

このアルゴリズムの動作をステップごとに見ていきましょう。

• 初回のイテレーション： 組み合わせの配列が空の場合は、文字セット自体を初期状態として使用します。
• 終了条件： 引数 $size が 1 になった時点で、目的の長さの組み合わせが完成しているため、そのまま結果を返します。
• 組み合わせの構築： 新しい配列 $new_combinations を用意し、既存の各組み合わせに対して文字セット内の全文字を連結します。これにより、文字数が1つ増えた新しい組み合わせが次々と生成されます。
• 再帰呼び出し： sampling() 関数は、文字セット・サイズ・組み合わせ配列の3つの引数を受け取り、サイズが1になるまで自分自身を繰り返し呼び出します。

例えば、要素数 n のセットからサイズ k の組み合わせを生成する場合、結果は n^k 件になります。上記の例では、3文字（a, b, c）からサイズ2の組み合わせを作っているため、3 × 3 = 9 通りの結果が出力されています。

なお、この実装では「aa」や「bb」のように同じ文字が重複する組み合わせも許容されます。もし重複を除外したい場合は、文字を連結する際にすでに使用済みの文字をスキップする条件分岐を追加するとよいでしょう。