您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

混合基數計數演算法：生成所有 n 位 m 進制數的高效迭代實作

編輯：關於C

源自 Knuth 《The Art of Computer Programming Vol.4》，此演算法以混合基數思想，通過單一陣列模擬多位計數器，以 O(1) 摊還時間生成下一組合，無需遞迴、無需多層迴圈，極其優雅高效。

演算法核心邏輯

陣列 a[1..n] 表示 n 位數，初始全 0
最低位 a[n] 每次 +1
若 a[j] == radix（達到基數），歸零並向高位進位 j--
重複直到最高位 a[1] 進位溢出（j==0），結束

關鍵技巧：分配 n+1 個元素，a[0] 作為哨兵，進位到 0 即為終止條件，省去額外判斷。

C 語言標準實作


void mixed_radix_count(int n, int radix, void (*callback)(int*, int)) {
    if (n <= 0 || radix <= 1) return;

    int* a = (int*)calloc(n + 1, sizeof(int)); // a[0] 哨兵，a[1..n] 數位
    if (!a) return;

    while (1) {
        callback(a + 1, n); // 傳遞有效數位起始位址

        int j = n;
        while (a[j] == radix - 1) { // 當前位達最大值
            a[j] = 0;               // 歸零
            --j;                    // 向高位進位
        }
        if (j == 0) break;          // 哨兵位被進位 → 全排列結束
        ++a[j];                     // 高位 +1
    }
    free(a);
}

使用範例：列印所有 3 位 3 進制數


void print_digits(int* digits, int n) {
    for (int i = 0; i < n; ++i) printf("%d", digits[i]);
    printf("\n");
}

int main() {
    mixed_radix_count(3, 3, print_digits);
    return 0;
}
// 輸出：
// 000
// 001
// 002
// 010
// 011
// ...
// 222

擴展：混合基數（每位基數不同）

Knuth 原演算法支援每位基數不同（如日期：日 30、月 12、年無上限）。只需將 radix 改為陣列 radices[1..n]：


void mixed_radix_general(int n, const int radices[], void (*cb)(int*, int)) {
    int* a = calloc(n + 1, sizeof(int));
    while (1) {
        cb(a + 1, n);
        int j = n;
        while (a[j] == radices[j] - 1) { a[j] = 0; --j; }
        if (j == 0) break;
        ++a[j];
    }
    free(a);
}