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

используйте положительное число для перечисления комбинаций и отрицательное число для их подсчета.

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.