給定數組 $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;
}
特點: 僅維護索引數組,無遞歸棧溢出風險,記憶體穩定。
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),不隨組合總數增長
| 實現方式 | 執行時間 (ms) | 峰值內存 (MB) | 適用場景 |
|---|---|---|---|
| 遞歸回溯 (原文方法一) | 238 | 18.5 | 教學、小數據 (n<15) |
| 遞歸回溯 (原文方法二) | 710 | 22.1 | array_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
PHP 實現排列組合,迭代索引法 是性能與可讀性的最佳平衡點;生成器 解決大規模組合的內存瓶頸。理解算法本質 (索引遞增/回溯),比死記代碼更重要。下次面對「從 N 個元素取 K 個」的需求,請優先拿起迭代索引法或生成器,拒絕暴力遞歸與 `sort()` 大法。