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

Algorithm for Generating Combinations from a Single Set

The task at hand is to devise an algorithm that can generate all possible combinations of a specified size from a given character set, effectively functioning as a sampling algorithm. Unlike permutation algorithms, this technique allows for the repetition of characters within combinations.

Recursive Approach

To tackle this problem, we employ a recursive function that takes as input the character set, the desired combination size, and an array of intermediate combinations (initialized as the original set for the initial iteration).

1. Base Case: If the size is 1, the function returns the current set of combinations.

2. Recursive Step:

   • Create an empty array for the new set of combinations.
   • For each existing combination and character in the set, concatenate them and append them to the new array.
   • Recall the same function with the updated character set (unchanged), reduced size, and new set of combinations as input.

Example Implementation

The following PHP code illustrates the implementation of the recursive algorithm:

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);

}

Example Usage

To demonstrate the functionality, let's consider a set of characters:

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

Using the algorithm, we can generate all combinations of size 2:

$output = sampling($chars, 2);
var_dump($output);

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