P(n,m) = n!/(n-m)!n! 種<?php
header("Content-Type: text/html; charset=utf-8");
/**
* 全排列遞歸生成器
* @param array $remaining 剩餘可選元素
* @param array $current 當前已構建排列
* @param array $original 原始元素集合 (用於計算剩餘)
* @return array 所有排列組成的二維數組
*/
function permute(array $remaining, array $current = [], array $original = null): array {
if ($original === null) $original = $remaining;
$results = [];
if (count($remaining) > 1) {
// 保存當前狀態用於回溯
$snapshot = $current;
foreach ($remaining as $value) {
// 選擇:加入當前排列
$current[] = $value;
// 計算新剩餘元素 (集合差集)
$newRemaining = array_diff($original, $current);
if (count($newRemaining) > 0) {
// 遞歸
$results = array_merge($results, permute($newRemaining, $current, $original));
}
// 回溯:恢復狀態
$current = $snapshot;
}
} elseif (count($remaining) === 1) {
// 遞歸終點:只剩一個元素,直接構建完整排列
$current[] = $remaining[0];
$results[] = implode('', $current); // 轉字符串或保持數組
}
return $results;
}
/** 遞歸輸出多維數組 */
function printRecursive(array $arr, int $depth = 0): int {
$count = 0;
foreach ($arr as $value) {
if (is_array($value)) {
$count += printRecursive($value, $depth + 1);
} else {
echo str_repeat(' ', $depth) . $value . "\n";
$count++;
}
}
return $count;
}
// 測試
$elements = ['A', 'B', 'C', 'D'];
$allPermutations = permute($elements);
echo "共 " . count($allPermutations) . " 種全排列:\n";
printRecursive($allPermutations);
ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA ... 共 24 種全排列
| 指標 | 複雜度 | 說明 |
|---|---|---|
| 時間 | O(n! × n) | n! 個排列,每個構建 O(n) |
| 空間 | O(n! × n) | 存儲所有結果;遞歸棧 O(n) |
⚠️ n ≥ 10 時 n! 爆炸增長 (10! = 3.6M),僅適合小規模集合 (n ≤ 8-9)。大規模需用生成器/迭代器按需產出。
<?php
function permuteGenerator(array $elements): Generator {
$n = count($elements);
$indices = range(0, $n - 1);
$cycles = array_reverse(range(1, $n));
yield array_map(fn($i) => $elements[$i], $indices);
while (true) {
for ($i = $n - 1; $i >= 0; $i--) {
$cycles[$i]--;
if ($cycles[$i] === 0) {
// 旋轉
$temp = $indices[$i];
array_splice($indices, $i, 1);
$indices[] = $temp;
$cycles[$i] = $n - $i;
} else {
$j = $cycles[$i];
// 交換
[$indices[$i], $indices[$n - $j]] = [$indices[$n - $j], $indices[$i]];
yield array_map(fn($k) => $elements[$k], $indices);
break;
}
}
// 檢查是否回到初始狀態
if ($indices === range(0, $n - 1)) break;
}
}
// 使用:按需迭代,不佔用巨大內存
foreach (permuteGenerator(['A','B','C','D']) as $perm) {
echo implode('', $perm) . "\n";
// 可隨時 break
}
<?php
// 使用 PHP 內置排列 (需安裝 math/combinatorics 或手工實現)
// 簡單場景:array_permutation 非內置,常用組合:
function combinations(array $arr, int $k): Generator {
$n = count($arr);
if ($k > $n) return;
$indices = range(0, $k - 1);
yield array_map(fn($i) => $arr[$i], $indices);
while (true) {
$i = $k - 1;
while ($i >= 0 && $indices[$i] === $i + $n - $k) $i--;
if ($i < 0) break;
$indices[$i]++;
for ($j = $i + 1; $j < $k; $j++) $indices[$j] = $indices[$j - 1] + 1;
yield array_map(fn($i) => $arr[$i], $indices);
}
}
全排列遞歸回溯是經典算法面試題。PHP 實現關鍵點:array_diff 計算剩餘元素、array_merge 合併結果、快照變量實現回溯。生產環境大數據量務必使用 Generator 生成器 逐個產出,避免內存耗盡。理解 array_diff 重建索引特性 (需 array_values 重置) 是避坑關鍵。