Printing a positional numeric system in C

Question

I'm trying to write a function that print a positional numeric system with given base and number of digits. For example, with Base = 2 and nDigits = 3 the output have to be like this:

000
001
010
011
...
111

Now, I've tried to do something but I've only failed. Consider that I can't store the numbers, I just have to print them, that's why I use a dynamic allocation of a 'support' array. That's what I tried to do so far, obviously not doing what it's intended to... I think the only correct part is to print all the combinations for Base^nDigits. (b=base, n=nDigits).

void printNumeration(int b, int n){
    int i, j=0;
    int *array = calloc(n, sizeof(int));

    if (array == NULL){
        printf("Allocation failed.\n");
        exit(0);
    }


    for (i=0; i<pow(b, n); i++){
        for (j=0; j<n; j++){
            printf("%d", array[j]);
            array[j]++;
            if (array[j] == n){
                array[j] = 0;
            }
        }
        printf("\n");
    }
}

You can also give some tips about a better solution if mine is completely wrong.

Answer 1

First of all, Do not use pow for integer numbers. - at least not without rounding. pow uses an inexact floating point algorithm to do the exponentiation. There was just last week a question where there was an error because pow(10, 2) was 99.9999999... which truncated to int was 99.

That is, there might well be a platform, where pow(2, 3) as in your example results in 7.999999...; as doubles are converted to integers by just truncating the decimals, this would mean that your code runs 7 loops instead of 8! The same would be still true for double comparison; 8.0 is still greater than 7.999999999999999. Thus we use round to ensure that the resulting number is rounded correctly to the nearest integer value (8.0 in this case).

Also you'd want to count this number beforehand, not for every loop iteration.

We have 2 inner loops. First prints the numbers and second works backwards - if the kth digit is equal to b we set it to 0, we decrease k by 1 and increase now kth digit by one, and repeat.

Finally, remember to free the memory allocated by calloc.

void printNumeration(int b, int n) {
    int *digits = calloc(sizeof(int), n);
    int max = round(pow(b, n));
    for (int i = 0; i < max; i ++) {
        for (int j = 0; j < n; j ++) {
            printf("%d", digits[j]);
        }
        int k = n - 1;
        digits[k] ++;
        while (k && digits[k] == b) {
            digits[k] = 0;
            k--;
            digits[k] ++;
        }
        printf("\n");
    }
    free(digits);
}

Answer 2

I did not understand 80% of what you said...

That's a bad ratio. Let me explain:

You increment each digit in the inner loop.

You increment every digit unconditionally in the inner loop and wrap it if necessary. That means that your enumeration increments all digits in lockstep, yielding output such as 00, 11, 22, 00, 11, 2, ...

You can either increment the last digit continuously (and calculate the carry) until the first digiit wraps (think odometer) ...

You can start with an array of all zeros. Print it. Increment the last digit. Check for overflow and if it overflows, set it to zero and increment the next digit, and so on. If the leftmost digit overflows, stop your enumeration. That's how an odometer (the mile/km counter) in a car works:

void printnum(int dig[], int n)
{
    static const char *digit = "0123456789abcdefghijklmnopqrstuvwxyz";

    while (n--) putchar(digit[dig[n]]);
    putchar('\n');
}

int enumerate(int base, int n)
{
    int dig[100] = {0};
    int count = 0;

    for (;;) {
        int i = 0;

        while (i < n && dig[i] == base) {
            dig[i++] = 0;
            dig[i]++;
        }
        if (i == n) break;

        printnum(dig, n);

        dig[0]++;
        count++;
    }

    return count;
}

or you can print i with the usual code to print integer of a cerian base for each pass.

Your enumeration yields base^n numbers. (You probably shouldn't calculate this power with the floating-point function pow, though.) You can loop over all these numbers as you do in your code and then print out the number in the given base. The usual approach, of which you can find zillions of examples here on SO, is to fill an array from the right with the remainders of subsequent divisions by base until the number is zero. Here, you want all digits printed, so you should do the division n times, regardless of the zero numerator.

int enumerate(int base, int n)
{
    int max = 1;
    int i;

    for (i = 0; i < n; i++) max *= base;

    for (i = 0; i < max; i++) {
        int buf[n];

        int j = i;
        int m;

        for (m = 0; m < n; m++) {
            buf[m] = j % base;
            j /= base;
        }

        printnum(buf, n);        
    }

    return max;
}

There are even more ways to solve this. Hours of fun!