如何使用递归方法从给定字符集生成特定大小的所有可能组合？

从单个集合生成组合的算法

当前的任务是设计一种算法，可以生成指定的所有可能组合给定字符集的大小，有效地充当采样算法。与排列算法不同，此技术允许组合中的字符重复。

递归方法

为了解决这个问题，我们采用递归函数，该函数将字符集、所需的组合大小和中间组合数组（初始化为初始迭代的原始集）。

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中文网其他相关文章！