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 

谢谢！

编辑 - 对不起，忘了提，零不包括在从0系列

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

5004号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); 
    } 
} 

调用用一个正数来枚举组合和一个负数来对它们进行计数。

Answer 2

函数next将数组a更新为下一个数字，并返回底部数字的值。 main函数遍历序列，一旦顶端数字为10就停止（因为一旦阵列用完，next只是不断递增最高有效位）。

该算法在单词中忽略边界检查可以被描述为“找到下一个数字，向底部数字加1，如果溢出找到下一个数字忽略底部数字，然后复制新的底部数字“。

#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.