再帰アルゴリズムを使用して、PHP で特定のセットのすべての組み合わせを生成するにはどうすればよいですか?

PHP のアルゴリズムを使用したすべての組み合わせの生成

コンピューター サイエンスの基本的なタスクの 1 つは、指定されたセットから組み合わせを生成することです。このコンテキストでは、組み合わせとは、指定されたサイズを持つ元のセットの要素のサブセットを指します。

たとえば、セット A = {A, B, C} について考えてみましょう。さまざまなサイズの組み合わせを取得する方法は次のとおりです。

再帰的アルゴリズムを使用した組み合わせの生成

この問題に取り組むために、考えられるすべての組み合わせを探索する再帰的アルゴリズムを採用できます。 。以下に段階的な内訳を示します。

1. 空の配列 $combinations を初期化して組み合わせを保存します。
2. $size が 1 に等しい場合、基本ケースに達しています。
3. $chars と現在の$combinations.
4. 各組み合わせと文字について、その文字を組み合わせに追加し、新しい組み合わせを $new_combinations に追加します。
5. 更新された $new_combinations でサンプリング関数を再帰的に呼び出し、$size をデクリメントします。 1.

での実装PHP

function sampling($chars, $size, $combinations = []) {
    if (empty($combinations)) {
        $combinations = $chars;
    }
    if ($size == 1) {
        return $combinations;
    }
    $new_combinations = [];
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }
    return sampling($chars, $size - 1, $new_combinations);
}

例

元のセット A = {A, B, を考えてみましょう。 C}.

$chars = ['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"
}

このアルゴリズムは、指定されたセットから特定のサイズのすべての組み合わせを生成する体系的なアプローチを提供します。その再帰的な性質により、入力セットのサイズに関係なく、考えられるすべての組み合わせを効率的に探索できます。

以上が再帰アルゴリズムを使用して、PHP で特定のセットのすべての組み合わせを生成するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。