CODEWITHSUNDEEP
calgorithmdigits
Bucknall
Bucknall

Reputation: 25

Unique Combinations of Digits in C

I need to design an algorithm in C to calculate unique combinations of digits for 0 to 1,000,000. For example, when 13 appears, 31 would not be included in this sequence. Can anyone help me find an algorithm to describe this? The first few numbers in the series would be:

 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

Thanks!

edit - Sorry, forgot to mention that zero isn't included

Upvotes: 2

Views: 2939

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58251

The function next updates the array a to the next number, returning the value of the bottom digit. The main function iterates through the sequence, stopping once the top digit is 10 (since once the array has been used up, next just keeps incrementing the most significant digit).

The algorithm, in words and ignoring bounds checking, could be described as "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;
}

You can count the solutions in O(N) time (where N is the number of digits). If K(n, d) is the number of solutions with exactly n digits, and whose top digit is 9-d, then K(0, d) = 1, and K(n+1, d) = K(n, 0) + K(n, 1) + ... + K(n, d). The number of solutions with n or fewer digits is then K(1, 8) + K(2, 8) + ... + K(n, 8). These observations yield this dynamic programming solution:

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

Gives:

there are 5004 numbers.

Upvotes: 2

chqrlie
chqrlie

Reputation: 144740

#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 numbers in the series from 0 to 1000000

A much quicker version:

#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 with a positive number to enumerate combinations and a negative number to just count them.

Upvotes: 6

Related Questions