C++ 遞歸實現全排列：從原理到代碼完整解析

C++ 遞歸實現全排列：從原理到代碼完整解析

全排列是經典的遞歸入門問題：給定 n 個互不相同的元素，輸出所有可能的排列順序。本文通過模板函數實現通用型全排列，並詳細剖析遞歸狀態轉移與剪枝邏輯。

問題建模

對於長度為 n 的序列，第一個位置有 n 種選擇，第二個位置剩 n-1 種，以此類推。遞歸函數需維護：

• num[]：剩餘可用元素池（已用元素置 0 標記）
• numC[]：當前已構建的排列前綴
• iUse：尚需填充的位置數
• sum：總排列計數器

遞歸框架

template <class T>
void ComBineNum(T *num, const int count, T *numC, int iUse, int *sum) {
    int iNull = 0;
    T *newNum = new T[count];
    for (int i = 0; i < count; ++i) {
        memcpy(newNum, num, count * sizeof(T)); // 複製當前狀態
        if (newNum[i] == 0) {                   // 元素已用過
            if (++iNull == count) {             // 所有元素皆用完 → 找到一個完整排列
                for (int k = 0; k < count; ++k) cout << numC[k];
                cout << endl;
                ++(*sum);
                delete[] newNum;
                return;
            }
            continue;
        }
        // 選擇 newNum[i] 放入當前位置
        numC[count - iUse] = newNum[i];
        newNum[i] = 0;                          // 標記已用
        ComBineNum(newNum, count, numC, iUse - 1, sum); // 遞歸填下一位
    }
    delete[] newNum;
}

關鍵細節解析

1. 狀態複製而非原地修改：每層遞歸 new T[count] 並 memcpy，避免回溯時需手動恢復狀態，代碼更清晰（空間換時間）。
2. 終止條件：iNull == count 表示池中無可用元素，當前 numC 即為一個完整排列。
3. 模板泛型：支援 char、int、string 等任意可複製類型。

主程序與驗證

int main() {
    int sum = 0;
    const int n = 4;
    char num[n], perm[n];
    for (int i = 0; i < n; ++i) num[i] = '1' + i; // 初始化 {'1','2','3','4'}
    ComBineNum<char>(num, n, perm, n, &sum);
    cout << "sum (recursive): " << sum << endl;
    // 階乘驗證
    sum = 1;
    for (int i = 1; i <= n; ++i) sum *= i;
    cout << "sum (n!): " << sum << endl;
    return 0;
}

輸出示例（n=4）

1234
1243
1324
1342
1423
1432
2134
...
4321
sum (recursive): 24
sum (n!): 24

複雜度與優化方向

• 時間：O(n! * n) —— 需生成 n! 個排列，每個拷貝/輸出 O(n)。
• 空間：遞歸深度 O(n)，每層分配 O(n) 臨時陣列，總空間 O(n²)。
• 優化：可改用 std::next_permutation（STL）或原地交換 + 回溯（空間 O(n)），避免重複分配內存。

總結

遞歸全排列是理解「狀態空間樹」與「回溯法」的絕佳範例。本文採用值傳遞式狀態複製，犧牲空間換取代碼簡潔與邏輯清晰，適合教學與快速原型；工程落地時建議改用原地交換或 STL 算法以提升性能。