再帰的アプローチを使用して、特定の文字セットから特定のサイズの可能な組み合わせをすべて生成するにはどうすればよいですか?

単一セットから組み合わせを生成するアルゴリズム

当面の課題は、指定されたセットのすべての可能な組み合わせを生成できるアルゴリズムを考案することです。指定された文字セットからサイズを抽出し、サンプリング アルゴリズムとして効果的に機能します。順列アルゴリズムとは異なり、この手法では組み合わせ内で文字を繰り返すことができます。

再帰的アプローチ

この問題に取り組むために、入力として受け取る再帰関数を採用します。文字セット、必要な組み合わせサイズ、および中間組み合わせの配列 (最初の反復で元のセットとして初期化)。

1. 基本ケース: サイズが 1 の場合、この関数は、現在の組み合わせセットを返します。

2. 再帰ステップ:

   • 新しい組み合わせセット用の空の配列を作成します。
   • セット内の既存の組み合わせと文字ごとに、それらを連結して新しい配列に追加します。
   • 更新された文字セット (変更されていない)、縮小されたサイズ、および新しい組み合わせセットを使用して同じ関数を呼び出します。

実装例

次の PHP コードは、再帰アルゴリズムの実装を示しています。

function sampling($chars, $size, $combinations = array()) {

    // Base case
    if (empty($combinations)) {
        $combinations = $chars;
    }

    // Size 1 case
    if ($size == 1) {
        return $combinations;
    }

    // Initialize new combinations array
    $new_combinations = array();

    // Generate new combinations by concatenating existing and new characters
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }

    // Recursive call
    return sampling($chars, $size - 1, $new_combinations);

}

使用例

機能を実証するために、一連の文字を考えてみましょう:

$chars = array('a', 'b', 'c');

アルゴリズムを使用すると、サイズ 2 のすべての組み合わせを生成できます。 :

$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 中国語 Web サイトの他の関連記事を参照してください。