Уникальные комбинации цифр в 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; } 
     } 
    } 
} 

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

Invoke с положительным числом, чтобы перечислять комбинации и отрицательное число, чтобы просто посчитать их.

Answer 2

Функция next обновляет массив a до следующего номера, возвращая значение нижней цифры. Функция main выполняет итерацию через последовательность, останавливаясь, как только верхняя цифра равна 10 (поскольку после того, как массив был использован, next просто продолжает увеличивать самую значимую цифру).

Алгоритм в словах и игнорирование проверки границ можно описать как «найти следующее число, добавить его к нижней цифре, и если он переполнит, найдет следующий номер, игнорируя нижнюю цифру, а затем дублирует новую нижняя цифра ".

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