C中数字的唯一组合

#include <stdio.h>
int main(void) {
    int i, n;
    for (n = 1; n < 1000000; n++) {
        for (i = n;;) {
            if (i / 10 % 10 > i % 10) break;
            if ((i /= 10) == 0) { printf("%d\n", n); break; }
        }
    }
}

5004个数字,从0到1000000

更快的版本:

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

static long long enumerate(char *p, int i, int n, int digit, int silent) {
    long long count = 0;
    if (i >= n) {
        if (!silent) printf("%s\n", p);
        return 1;
    }
    for (p[i] = digit; p[i] <= '9'; p[i]++)
        count += enumerate(p, i + 1, n, p[i], silent);
    return count;
}

int main(int argc, char **argv) {
    char array[256];
    int i, n;
    int max = (argc > 1) ? strtol(argv[1], NULL, 0) : 6;
    int silent = 0;
    long long count = 0;
    if (max < 0) {
        max = -max;
        silent = 1;
    }
    array[sizeof(array)-1] = '\0';
    for (n = 1; n <= max; n++) {
        count += enumerate(array + sizeof(array) - 1 - n, 0, n, '1', silent);
        if (silent)
            printf("%lld combinations between 0 and 1E%d\n", count, n);
    }
}

使用正数调用以枚举组合,使用负数仅计数组合。

函数 next 更新阵列 a 返回底部数字的值。这个 main 函数在序列中迭代,当顶部数字为10时停止(因为一旦数组用完, 下一个 仅保持递增最高有效数字)。

该算法可以用忽略边界检查的方式描述为“找到下一个数字,在底部数字上加一个,如果溢出,则忽略底部数字找到下一数字,然后复制新的底部数字。”

#include <stdio.h>

int next(int *a, size_t len) {
    if (*a == 9 && len > 1) {
        *a = next(a-1, len-1);
    } else {
        *a += 1;
    }
    return *a;
}

#define N 6

int main(int argc, char *argv[]) {
    int a[N] = {0};
    while (next(a+N-1, N) != 10) {
        for (int i = 0; i < N; i++) {
            if (a[i] != 0) printf("%d", a[i]);
        }
        printf("\n");
    }
    return 0;
}

您可以在O(N)时间内计算解(其中N是位数)。如果K(n,d)是正好有n位数字的解的数目,并且其顶部数字是9-d,则K(0,d)=1,并且K(n+1,d)=K(n)+K(n、1)+…+K(n,d)。n位数或更少位数的解的数目是K(1,8)+K(2,8)+…+K(n,8)。这些观察结果产生了动态编程解决方案:

int count(int n) {
    int r[9] = {1};
    int t = 0;
    for (int i = 0; i < n+1; i++) {
        for (int j = 1; j < 9; j++) {
            r[j] += r[j-1];
        }
        t += r[8];
    }
    return t - 1;
}

int main(int argc, char* argv[]) {
    printf("there are %d numbers.\n", count(6));
    return 0;
}

给予:

there are 5004 numbers.