混合基數計數算法：生成 n 位 m 進制所有整數的 C 語言高效實現

問題定義

給定位數 n、基數 m（m 進制），生成所有從 0...0 到 (m-1)...(m-1) 的 n 位數。例如 n=3, m=2 生成 000, 001, 010, 011, 100, 101, 110, 111。

算法核心：模擬加法進位

1. 陣列 a[0..n] 初始化為 0，a[0] 作為哨兵位（進位溢出終止標誌）
2. 最低位 a[n]++
3. 若 a[j] == m，置 0 向高位進位 j--，重複
4. 若進位傳播至 a[0]（j==0），全排列結束

完整 C 語言實現

#include <stdlib.h>
#include <stdio.h>

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

void mixed_radix_num(int n, int radix) {
    int* a = (int*)malloc(sizeof(int) * (n + 1)); // a[0] 哨兵
    if (!a) return;
    for (int j = 0; j <= n; ++j) a[j] = 0;

    while (1) {
        print_num(a, n);       // 輸出當前組合
        int j = n;
        while (a[j] == radix - 1) { // 達到最大值需進位
            a[j] = 0;
            --j;
        }
        if (j == 0) break;     // 哨兵位被修改 → 全排列結束
        ++a[j];                // 進位成功
    }
    free(a);
}

int main() {
    mixed_radix_num(3, 2); // 3 位二進制
    return 0;
}

關鍵設計點解析

1. 哨兵位 a[0] 的妙用

• 統一了「正常進位」與「溢出終止」的判斷邏輯
• 避免額外旗標變數或複雜邊界檢查
• 源自 Knuth《計算機程序設計藝術》第 4 卷經典技巧

2. 遞增邏輯的簡潔性

while (a[j] == radix-1) { a[j]=0; j--; } 一行處理連續進位，if (j==0) break; 一行判斷結束。無需巢狀迴圈或複雜狀態機。

3. 空間複雜度 O(n)，時間複雜度 O(mⁿ)

最優：必須輸出 mⁿ 個結果，無法更快。記憶體僅需 n+1 個整數。

推廣：混合基數（每位基數不同）

若第 i 位基數為 rᵢ（如日期：年無限、月 12、日 31、時 24、分 60），只需將 radix-1 改為 radix[j]-1，radix 變為陣列即可。同樣優雅處理進位。

應用場景

• 全排列/組合生成器
• 多維陣列線性化索引遍歷
• 暴力破解密碼空間枚舉
• 狀態空間搜尋（如八數碼、魔方狀態編碼）
• 測試用例自動生成（參數組合覆蓋）

總結

混合基數計數算法以「哨兵位 + 就地進位」極簡邏輯，實現任意基數、任意位數的全域遍歷。代碼短小、無遞歸、無額外狀態、易擴展混合基數，是組合生成類問題的標準參考實現。掌握其精髓，舉一反三解決各類計數枚舉問題。