全排列算法新視角：編號到排列的直接映射與 O(1) 空間遍歷

傳統全排列生成依賴遞歸/回溯/字典序次排列。本文介紹一種基於編號的直接映射算法：給定索引 k (0 ≤ k < n!)，經過 n 輪「除法+取模+交換」直接得到第 k 個排列，無需生成前驅排列，支援隨機存取與 O(1) 空間遍歷。

核心洞察

以 n=4，元素 {0,1,2,3} 為例：

• 全排列共 4! = 24 個，編號 0~23。
• 末位固定為 0 的有 3! = 6 個，前綴為 {1,2,3} 的全排列。
• 同理末位 1、2、3 各佔 6 個，前綴為剩餘三元素全排列。
• 問題遞歸化為：確定末位 → 剩餘元素遞歸求排列。

算法步驟 (以編號 13 為例)

1. 初始有序陣列：[0, 1, 2, 3]。
2. 第 1 輪 (決定末位) : idx = [13 / 3!] + 1 = [13/6]+1 = 2+1 = 3 → 取第 3 個元素(下標 2)即 2 為末位。
   交換 a[2] ↔ a[3] → 陣列 [0, 1, 3, 2] (藍色已定)。
   新編號 k = 13 % 6 = 1。
3. 第 2 輪 (決定倒數第 2 位) : idx = [1 / 2!] + 1 = [1/2]+1 = 0+1 = 1 → 取第 1 個元素 0。
   交換 a[0] ↔ a[2] → [3, 1, 0, 2]。
   新編號 k = 1 % 2 = 1。
4. 第 3 輪 : idx = [1 / 1!] + 1 = 2 → 取第 2 個元素 1。
   交換 a[1] ↔ a[1] (無變化) → [3, 1, 0, 2]。
   新編號 k = 1 % 1 = 0。
5. 第 4 輪 : 僅剩 3，直接確定。
   最終排列：3, 1, 0, 2。

完整映射表 (n=4)

編號 → 排列
0  → 1 2 3 0
1  → 2 1 3 0
2  → 2 3 1 0
3  → 3 1 2 0
4  → 3 2 1 0
5  → 3 2 0 1
6  → 2 3 0 1
7  → 2 0 3 1
8  → 0 2 3 1
9  → 3 0 2 1
10 → 0 3 2 1
11 → 1 0 3 2
12 → 1 3 0 2
13 → 3 1 0 2  ← 例
14 → 3 0 1 2
15 → 0 3 1 2
16 → 1 0 2 3
17 → 0 1 2 3
18 → 1 2 0 3
19 → 2 1 0 3
20 → 2 0 1 3
21 → 0 2 1 3
22 → 1 0 2 3
23 → 0 1 2 3

三大應用優勢

代碼實現 (C)

void decode(int k, int *a, int n) {
    // a 必須預先填入 0..n-1 或任意有序初始排列
    for (int i = n; i >= 2; i--) {
        int fact = 1;
        for (int j = 2; j < i; j++) fact *= j;  // (i-1)!
        int idx = k / fact;                     // 0-based
        k %= fact;
        // 將第 idx 個元素移至位置 i-1
        int tmp = a[idx];
        for (int j = idx; j < i-1; j++) a[j] = a[j+1];
        a[i-1] = tmp;
    }
}

與康托展開的關係

本算法本質上是康托展開的逆運算（解碼）。康托展開將排列編碼為索引，本算法將索引解碼為排列。兩者同構，時間複雜度均為 O(n²)（含階乘計算），可預計算階乘表優化至 O(n)。

結語

編號→排列直接映射，將「生成序列」轉化為「隨機存取」，解鎖並行、隨機采樣、分布式處理等高階用法。掌握康托展開雙向轉換，是組合算法工程化的關鍵技能。