如何使用遞歸演算法在 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, 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中文網其他相關文章！