全排列遞歸算法深度解析：三種核心思路與代碼實現

全排列遞歸算法深度解析：三種核心思路與代碼實現

全排列是算法入門必學問題，也是面試高頻考點。給定 n 個互不相同的元素，輸出所有 n! 種排列。本文系統梳理三種主流遞歸思路。

問題定義

輸入：1 2 3 → 輸出：123, 132, 213, 231, 312, 321（共 6 = 3! 種）

方法一：訪問標記法（最直觀，易擴展）

思想：維護 used[] 標記哪些數已用，遞歸填坑位 pos。每層嘗試所有未用數字，填入後遞歸下一層，回溯時撤銷標記。

void dfs(int pos) {
    if (pos == n) { output(); return; }
    for (int i = 0; i < n; i++)
        if (!used[i]) {
            used[i] = 1;
            perm[pos] = i;
            dfs(pos + 1);
            used[i] = 0;  // 回溯：還原現場
        }
}

優點：邏輯清晰，易修改約束條件（如去重、條件剪枝）。

方法二：交換法（原地操作，空間優）

思想：觀察 123 的全排列 = 1 + perm(23) + 2 + perm(13) + 3 + perm(12)。遞歸時將第 k 位依次與後面每個位置交換，遞歸處理 k+1，回溯時交換回去。

void perm(char* s, int k, int m) {
    if (k == m) { output(s); return; }
    for (int i = k; i <= m; i++) {
        swap(s[k], s[i]);
        perm(s, k + 1, m);
        swap(s[k], s[i]);  // 恢復現場
    }
}

優點：無額外 used 數組，原地操作，常數因子小。

方法三：字典序遞推法（非遞歸，可求下一排列）

思想：從當前排列生成字典序下一個：

1. 從右向左找第一個 a[i] < a[i+1] 的位置 i
2. 從右向左找第一個 a[j] > a[i] 的位置 j
3. 交換 a[i], a[j]
4. 反轉 i+1 到末尾

C++ STL next_permutation 即此算法。效率極高，適合需按序枚舉或求第 k 個排列的場景。

代碼對比與選擇建議

常見變體

• 含重複元素全排列：排序後，交換法中跳過相同元素（if (i != k && s[i] == s[k]) continue;）
• 部分排列 (k-permutation)：遞歸深度限制為 k
• 下一排列 / 第 k 個排列：用字典序法或康托展開

總結

理解全排列的本質是「有序選擇 + 回溯」，三種方法本質相同，只是實現細節不同。面試時能手寫任一種並說清回溯點、剪枝條件即可；工程中優先用 next_permutation 或成熟庫。