字母全排列快速算法：插入法生成所有組合的 C 語言實現

問題定義

給定字符串（如 "ABC"），生成所有非空子集的全排列。
輸出示例：A, AB, AC, ABC, ACB, B, BA, BC, BAC, BCA, C, CA, CB, CAB, CBA。

核心思想：遞歸插入法

假設已有前 k-1 個字符的所有排列集合 S_{k-1}。
第 k 個字符 c_k 可插入到每個排列的 0..len 任意位置，生成新排列。
如 "AB" 插入 'C' → "CAB", "ACB", "ABC"。

算法流程

1. 計算總組合數 Total = Σ_{i=1}^n P(n,i)（n≤10 時 Total < 10^6）。
2. 分配連續內存 buf[Total][n+1] 存儲所有字符串（以 \0 結尾）。
3. 迭代插入：

char *allPerm(char *str, int *count) {
    int n = strlen(str);
    int total = 0;
    for (int i = 1, p = 1; i <= n; ++i) {
        p *= i;
        total += p;
    }
    char *buf = malloc(total * (n+1));
    int cnt = 0;
    for (int k = 0; k < n; ++k) {  // 插入第 k 個字符
        int old = cnt;
        for (int i = 0; i < old; ++i) {
            char *src = buf + i*(n+1);
            int len = strlen(src);
            for (int pos = 0; pos <= len; ++pos) {
                char *dst = buf + cnt++*(n+1);
                memcpy(dst, src, pos);
                dst[pos] = str[k];
                memcpy(dst+pos+1, src+pos, len-pos+1);  // 含 \0
            }
        }
        if (old == 0) {  // 第一個字符
            buf[cnt][0] = str[0];
            buf[cnt++][1] = '\0';
        }
    }
    *count = cnt;
    return buf;
}

性能測試

• n=10 字符，總排列數 9864100，單次運行約 0.5 秒（視機器而定）。
• 內存佔用 Total * (n+1) 字節，n=10 約 100 MB，需注意記憶體限制。

優化方向

1. 迭代器模式：不存儲所有結果，按需生成（如 `next_permutation` 風格），極大節省內存。
2. 位掩碼 + 排序：枚舉子集掩碼，對每個子集 `next_permutation`。
3. 遞歸回溯：經典 DFS + `used[]` 數組，代碼最簡潔，適合教學。

經典遞歸回溯參考

void dfs(char *str, int n, int depth, char *path, int *used) {
    if (depth > 0) { path[depth] = '\0'; puts(path); }
    for (int i = 0; i < n; ++i) if (!used[i]) {
        used[i] = 1;
        path[depth] = str[i];
        dfs(str, n, depth+1, path, used);
        used[i] = 0;
    }
}

時間複雜度相同，但空間僅 O(n) 遞歸棧，工程上更推薦。