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.