萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 全排列演算法六大實作:遞迴交換、遞迴鏈接、回溯法與非遞迴優化完整解析

前言

全排列時間複雜度為 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;
}

演算法五:Heap's Algorithm(最小交換次數)

核心思想:每次僅交換兩個元素產生新排列,總交換次數最少,效能最優。

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;
}

演算法六:ES6 生成器實作(惰性求值)

核心思想:使用 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 AlgorithmO(n!)O(n)交換次數最少、最快邏輯較抽象效能敏感場景
生成器O(n!) 總計O(n) 常數惰性、可中斷需 ES6+ 環境串流處理、只需前 k 組

實務建議

  1. n ≤ 8:任選皆可,推薦 遞迴交換 可讀性最好
  2. n > 10:避免一次產生所有排列,改用生成器或 Heap's Algorithm 分批處理
  3. 需剪枝/約束:回溯法 最易加入條件判斷
  4. 生產環境:考慮引入 lodash.permutations 或 permutation.js 成熟庫
copyright © 萬盛學電腦網 all rights reserved