如何使用递归算法在 PHP 中生成给定集合的所有组合？

使用 PHP 中的算法生成所有组合

计算机科学的基本任务之一是从给定的集合生成组合。在这种情况下，组合是指原始集合中具有指定大小的元素子集。

例如，考虑集合 A = {A, B, C}。以下是我们如何获得各种大小的组合：

使用递归算法生成组合

为了解决这个问题，我们可以采用递归算法来探索所有可能的组合。下面是一步一步的分解：

1. 初始化一个空数组 $combinations 来存储组合。
2. 如果 $size 等于 1，我们就达到了基本情况并且可以返回 $combinations。
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中文网其他相关文章！