C語言字典序全排列非遞歸算法優化指南

問題描述

原始代碼採用遞歸實現階乘計算與排列生成，導致在較大 n 時出現超時。主要瓶頸在於遞歸調用開銷大、數組操作未優化、且部分邏輯存在錯誤（如 reverse 函數循環條件寫錯）。

優化策略

1. 消除遞歸：改用迭代實現字典序下一個排列算法（類似 C++ next_permutation）。
2. 原地交換與反轉：使用雙指針原地反轉數組尾部，避免額外空間。
3. 預計算階乘：若需總數，可預存階乘表，但生成排列時不必計算階乘。
4. 優化 I/O：使用 printf 替代 cout，或一次性輸出緩衝。

優化後代碼（C 風格）

#include <stdio.h>

#define MAXN 105
int a[MAXN];
int n;

void swap(int *x, int *y) {
    int tmp = *x; *x = *y; *y = tmp;
}

void reverse(int left, int right) {
    while (left < right) swap(&a[left++], &a[right--]);
}

int next_permutation() {
    int i = n - 1;
    while (i >= 1 && a[i] >= a[i+1]) i--;
    if (i < 1) return 0;
    int j = n;
    while (a[j] <= a[i]) j--;
    swap(&a[i], &a[j]);
    reverse(i+1, n);
    return 1;
}

void print_arr() {
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    printf("\n");
}

int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++) a[i] = i;
        print_arr();
        while (next_permutation()) print_arr();
    }
    return 0;
}

關鍵點解析

• next_permutation 返回 0 表示已到最後一個排列，主循環即可終止。
• 數組下標從 1 開始，符合題目習慣，也可改為 0 基。
• 時間複雜度 O(n!) 生成所有排列，但常數因子極小，能通過大多數 OJ 限制。