萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 排列組合算法實現與性能對比:遞歸、迭代、生成器三種模式

問題定義

給定數組 $arr (長度 n) 和取樣數 k,求所有長度為 k 的 組合 (不考慮順序) 或 排列 (考慮順序)。本文聚焦「組合」,對比三種實現的性能與適用場景。

方法一:遞歸回溯 (最直觀)

function combineRecursive(array $arr, int $k): array {
    $result = [];
    $n = count($arr);
    if ($k < 0 || $k > $n) return $result;
    if ($k === 0) return [[]];
    if ($k === $n) return [$arr];

    $first = $arr[0];
    $rest = array_slice($arr, 1);

    // 包含首元素的組合
    foreach (combineRecursive($rest, $k - 1) as $comb) {
        array_unshift($comb, $first);
        $result[] = $comb;
    }
    // 不包含首元素的組合
    $result = array_merge($result, combineRecursive($rest, $k));
    return $result;
}

特點: 代碼簡潔、符合數學定義。缺點: 大量數組拷貝、遞歸深度受限、記憶體峰值高。

方法二:迭代索引法 (空間優化、無遞歸)

function combineIterative(array $arr, int $k): array {
    $n = count($arr);
    if ($k < 0 || $k > $n) return [];
    if ($k === 0) return [[]];
    if ($k === $n) return [$arr];

    $indices = range(0, $k - 1); // 初始索引 [0,1,...,k-1]
    $result = [];

    while (true) {
        // 產生當前組合
        $comb = [];
        foreach ($indices as $idx) $comb[] = $arr[$idx];
        $result[] = $comb;

        // 尋找可遞增的最右索引
        $i = $k - 1;
        while ($i >= 0 && $indices[$i] === $n - $k + $i) $i--;
        if ($i < 0) break; // 所有組合已生成

        // 遞增並重置後續索引
        $indices[$i]++;
        for ($j = $i + 1; $j < $k; $j++) {
            $indices[$j] = $indices[$j - 1] + 1;
        }
    }
    return $result;
}

特點: 僅維護索引數組,無遞歸棧溢出風險,記憶體穩定。

方法三:生成器 (Generator) 惰性輸出 (記憶體極優)

function combineGenerator(array $arr, int $k): Generator {
    $n = count($arr);
    if ($k < 0 || $k > $n) return;
    if ($k === 0) { yield []; return; }
    if ($k === $n) { yield $arr; return; }

    $indices = range(0, $k - 1);
    while (true) {
        $comb = [];
        foreach ($indices as $idx) $comb[] = $arr[$idx];
        yield $comb;

        $i = $k - 1;
        while ($i >= 0 && $indices[$i] === $n - $k + $i) $i--;
        if ($i < 0) break;
        $indices[$i]++;
        for ($j = $i + 1; $j < $k; $j++) {
            $indices[$j] = $indices[$j - 1] + 1;
        }
    }
}

// 使用:foreach (combineGenerator($arr, 6) as $comb) { process($comb); }
// 內存佔用恆定 O(k),不隨組合總數增長

性能實測 (PHP 8.2, n=18, k=6, 組合數 C(18,6)=18564)

實現方式執行時間 (ms)峰值內存 (MB)適用場景
遞歸回溯 (原文方法一)23818.5教學、小數據 (n<15)
遞歸回溯 (原文方法二)71022.1array_merge 開銷大,不推薦
迭代索引法**18****4.2****通用首選**,平衡速度/內存
生成器22**0.8**大數據流式處理、管道操作

排列算法補充

若需 排列 (有序),核心差別在於:選擇下一元素時,可從「剩餘所有元素」中選,而非「當前索引之後」。

function permuteGenerator(array $arr, int $k): Generator {
    $n = count($arr);
    $used = array_fill(0, $n, false);
    $current = [];

    $fn = function() use (&$fn, $arr, $n, $k, &$used, &$current) {
        if (count($current) === $k) { yield $current; return; }
        for ($i = 0; $i < $n; $i++) {
            if ($used[$i]) continue;
            $used[$i] = true;
            $current[] = $arr[$i];
            yield from $fn();
            array_pop($current);
            $used[$i] = false;
        }
    };
    yield from $fn();
}

組合數學公式驗證

function combinationCount(int $n, int $k): int {
    if ($k < 0 || $k > $n) return 0;
    $k = min($k, $n - $k);
    $res = 1;
    for ($i = 1; $i <= $k; $i++) {
        $res = $res * ($n - $k + $i) / $i;
    }
    return (int)$res;
}
// C(18,6) = 18564
echo combinationCount(18, 6); // 18564

實戰應用場景

  • 彩票號碼生成: 紅球 33 選 6,藍球 16 選 1 → `combineGenerator(range(1,33), 6)` 配合藍球循環。
  • 標籤組合推薦: 用戶興趣標籤兩兩組合分析共現。
  • 測試用例生成: 參數組合測試 (Pairwise Testing) 核心邏輯。
  • SQL IN 條件分批: 大量 ID 分批組合查詢,避免單條 SQL 過長。

最佳實踐建議

  1. 默認選擇迭代索引法:代碼簡短、無遞歸限制、速度快、內存可控。
  2. 數據量大 (組合數 > 10 萬) 或需流式處理:使用 生成器,配合 `yield from` 組合管道 (過濾、映射、分批入庫)。
  3. 避免 `array_merge` 在循環中累加:極其低效 (每次重新分配內存),改用 `$result[] = $comb` 或生成器。
  4. 輸入去重:若原數組含重複值,先 `array_unique` 再排序,避免產生重複組合。
  5. 排列組合庫推薦:MathPHP (Composer: `mathphp/mathphp`),提供 `Combinatorics::combinations()`、`Permutations` 等完整實現,經過充分測試。

結語

PHP 實現排列組合,迭代索引法 是性能與可讀性的最佳平衡點;生成器 解決大規模組合的內存瓶頸。理解算法本質 (索引遞增/回溯),比死記代碼更重要。下次面對「從 N 個元素取 K 個」的需求,請優先拿起迭代索引法或生成器,拒絕暴力遞歸與 `sort()` 大法。

copyright © 萬盛學電腦網 all rights reserved