全排列時間複雜度為 O(n!),是經典演算法面試題與組合數學基礎。本文整理六種 JavaScript 實作,從基礎遞迴到非遞迴回溯,附完整可執行代碼與核心邏輯解析。
const elements = ['e1', 'e2', 'e3', 'e4']; // 4! = 24 種排列
核心思想:固定第 n 位,將剩餘元素依序交換至第 n 位,遞迴處理 n+1 位,回溯時交換回復。
function permuteSwap(arr) {
const result = [];
const a = [...arr];
function swap(i, j) {
if (i !== j) [a[i], a[j]] = [a[j], a[i]];
}
function backtrack(n) {
if (n === a.length - 1) {
result.push([...a]);
return;
}
for (let i = n; i < a.length; i++) {
swap(i, n);
backtrack(n + 1);
swap(i, n); // 回溯還原
}
}
backtrack(0);
return result;
}
特點:原地交換,空間效率高;遞迴深度 n,適合 n < 10。
核心思想:維護「剩餘元素池」與「已選序列」,每次從池中取一元素加入序列,遞迴直到池為空。
function permuteLink(arr) {
const result = [];
function backtrack(remaining, path) {
if (remaining.length === 0) {
result.push(path);
return;
}
for (let i = 0; i < remaining.length; i++) {
const next = remaining[i];
const newRemaining = [...remaining.slice(0, i), ...remaining.slice(i + 1)];
backtrack(newRemaining, [...path, next]);
}
}
backtrack(arr, []);
return result;
}
特點:不修改原陣列,語意清晰,但頻繁建立新陣列,記憶體開銷大。
核心思想:建立索引陣列 index[i] 表示第 i 位選擇的原始元素索引,透過回溯搜尋所有合法索引排列。
function permuteBacktrackRecursive(arr) {
const result = [];
const n = arr.length;
const index = Array(n).fill(-1);
function isValid(pos) {
for (let i = 0; i < pos; i++) {
if (index[i] === index[pos]) return false;
}
return true;
}
function seek(pos) {
if (pos >= n) {
result.push(index.map(i => arr[i]));
return;
}
for (index[pos] = 0; index[pos] < n; index[pos]++) {
if (isValid(pos)) {
seek(pos + 1);
}
}
index[pos] = -1; // 重置
}
seek(0);
return result;
}
核心思想:用迴圈模擬遞迴調用棧,手動管理位置指標與回溯狀態,避免呼叫棧溢位。
function permuteBacktrackIterative(arr) {
const result = [];
const n = arr.length;
const index = Array(n).fill(-1);
let pos = 0;
while (pos >= 0) {
index[pos]++;
if (index[pos] === n) {
index[pos] = -1;
pos--; // 回溯
continue;
}
// 檢查是否重複
let conflict = false;
for (let i = 0; i < pos; i++) {
if (index[i] === index[pos]) { conflict = true; break; }
}
if (conflict) continue;
if (pos === n - 1) {
// 找到一組完整排列
result.push(index.map(i => arr[i]));
} else {
pos++; // 前進下一位
}
}
return result;
}
核心思想:每次僅交換兩個元素產生新排列,總交換次數最少,效能最優。
function permuteHeap(arr) {
const result = [];
const a = [...arr];
const n = a.length;
const c = Array(n).fill(0); // 計數器陣列
result.push([...a]);
let i = 0;
while (i < n) {
if (c[i] < i) {
const j = (i % 2 === 0) ? 0 : c[i];
[a[i], a[j]] = [a[j], a[i]];
result.push([...a]);
c[i]++;
i = 0;
} else {
c[i] = 0;
i++;
}
}
return result;
}
核心思想:使用 function* 與 yield 逐個產生排列,記憶體常數級,適合處理大規模排列(僅需前幾組)。
function* permuteGenerator(arr) {
const a = [...arr];
const n = a.length;
const c = Array(n).fill(0);
yield [...a];
let i = 0;
while (i < n) {
if (c[i] < i) {
const j = (i % 2 === 0) ? 0 : c[i];
[a[i], a[j]] = [a[j], a[i]];
yield [...a];
c[i]++;
i = 0;
} else {
c[i] = 0;
i++;
}
}
}
// 使用方式
const gen = permuteGenerator(['e1','e2','e3','e4']);
console.log(gen.next().value); // 第一組
console.log(gen.next().value); // 第二組
// ... 按需取用,不一次產生所有
| 演算法 | 時間複雜度 | 空間複雜度 | 優點 | 缺點 | 建議場景 |
|---|---|---|---|---|---|
| 遞迴交換 | O(n!) | O(n) 棧 + O(n!) 結果 | 原地操作,好理解 | 遞迴深度限制 | 教學、n < 10 |
| 遞迴鏈接 | O(n!) | O(n²) 中間陣列 | 函數式、無副作用 | 記憶體壓力大 | 函數式偏好專案 |
| 遞迴回溯 | O(n!) | O(n) | 邏輯嚴謹 | 程式碼較繁瑣 | 需驗證約束條件 |
| 非遞迴回溯 | O(n!) | O(n) | 無棧溢位風險 | 迴圈邏輯較難寫 | 大 n、嵌入式環境 |
| Heap's Algorithm | O(n!) | O(n) | 交換次數最少、最快 | 邏輯較抽象 | 效能敏感場景 |
| 生成器 | O(n!) 總計 | O(n) 常數 | 惰性、可中斷 | 需 ES6+ 環境 | 串流處理、只需前 k 組 |
lodash.permutations 或 permutation.js 成熟庫