C 中数字的唯一组合

Question

我需要用 C 语言设计一个算法来计算 0 到 1,000,000 的唯一数字组合。例如，当出现 13 时，31 将不会包含在该序列中。谁能帮我找到一个算法来描述这个？该系列的前几个数字是：

 1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19,22,23,24,25,26,27,28,29,33,etc

谢谢！

编辑 - 抱歉，忘了说不包括零

Answer 1

#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; }
        }
    }
}

0 到 1000000 系列中的 5004 个数字

更快的版本：

#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] = '[=11=]';
    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);
    }
}

调用一个正数来枚举组合，用一个负数来计算它们。

Answer 2

函数next将数组a更新为下一个数字，返回底部数字的值。 main 函数遍历序列，一旦最高数字为 10 就停止（因为一旦数组用完，next 只会继续递增最高有效数字）。

该算法，用文字和忽略边界检查，可以描述为 "to find the next number, add one to the bottom digit, and if it overflows find the next number ignoring the bottom digit, and then duplicate the new bottom digit."

#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, 0) + 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.

C 中数字的唯一组合

Unique Combinations of Digits in C

c

algorithm

digits