Arbitrary Digit Counter

Question

I need a counter algortihm which use arbitrary given digits for counting purpose.

My code is similar to this:

static char digits[] = {'x','y','z'}; /* Arbitrary number of arbitrary digits. */
int i;
for(i=0; i<100; i++) {
    printf("%s\n", get_next());
}

My expected output:

x
y
z
yx
yy
yz
zx
zy
zz
yxx
yxy
yxz
yyx
yyy
yyz
yzx
yzy
yzz
zxx
... and so on

As you see, I need algorithm for implementing get_next() function, so using C language is not the point.

Edit I for clarification purpose:

My get_next() function may similar to this:

char get_next() {
    static previous = digits[0];
    char *next_number;

    /* do something here using previous and digits[] */

    return next_number;
}

Note that using get_next(void) or next(previous_number) or next(digits, previous_number) prototype for your function which generates next number is not important for me.

Edit II for clarification purpose:

My real scenario is more complex from the simple example above, I need a generic solution that works with arbitrary number of arbitrary digits.

Example digit inputs:

static char digits[] = {'a', 'b', 'c', ... 'z', '0', '1', ...}; /* Lots of digits */
static char digits[] = {'s','t','a','c','k','o','v','e','r'};   /* Arbitrary sequence */

Answer 1

char *get_next()
{
  static char str[10];
  static int i=0;
  int radix = 3; // size of array
  itoa(i,str,radix); // create base-3 representation
  char *p = &str[0];
  while( *p )
  {
    *p = digits[*p-'0']; // convert to the xyz scheme, breaks if radix>10
    p++;
  }
  i++;
  return str;
}

Answer 2

It's quite simple. You want to convert into base digit_count and then instead of converting the digits to numbers, you index into your array.

To convert to an arbitrary base, you need to division and remainder.

Here's a better version then what I used before because it actually creates a buffer (rather then prints it out), drops recursion for iteration and is in correct C instead of my previous C/Python hodgepodge.

Because it uses a static buffer, the code is not thread safe. Also note that there is no error checking that the code doesn't underflow the buffer if the number is too large. Finally, it uses a trick of building the string from the end to the front and returning a pointer to the middle of the buffer so it doesn't have to reverse the digits at the end.

char *getnum(int x)
{
    static char buffer[1024];
    int idx = 1024;

    buffer[--idx] = '\0';

    if (x == 0)
        buffer[--idx] = digits[0];
    else
    {
        while (x != 0)
        {
            buffer[--idx] = digits[x % digit_count];
            x /= digit_count;
        }
    }    

    return buffer + idx;
}

Answer 3

Your question can be split into two parts:

1. convert an integer to its representation in an arbitrary base, n, and
2. given n symbols, print the representation above.

The second part is obviously very easy. If you have a representation of a number in a given base, and the symbols that you want to use in such a base, then printing them out is just printing things in a loop.

To get an integer's representation in a given base, we will use an array of ints, with the values representing the digits, and the indices representing the places. We also need to store the number of valid digits. Also, we are assuming that we're dealing with positive numbers only, since that's what you seem to suggest in your question.

#define MAX 128 /* maximum number of digits in the final representation */

/* abstract representation of a number in a given base.
   `n` is the number of valid digits in the representation, and
   `digits` stores the digits in reverse order */
struct rep {
    int digits[MAX]; /* change as needed, or dynamically allocate */
    size_t n;
};

Then, let's write a function to convert a number to its representation. Since it's easier to return a reversed representation, we will return that, and then print in reverse order too:

/* convert a number `n` to its (reversed) representation in base `base`,
   and return the result in `ret`. */
void convert(int n, size_t base, struct rep *ret)
{
    size_t i = 0;
    do {
        ret->digits[i++] = n % base;
        n /= base;
    } while (n > 0 && i < MAX);
    ret->n = i;
}

Having done this, let's write a function to print the representation:

/* return a string representation of `num` in base `ndigits`, with `digits`
   representing the symbols */
char *next(const char *digits, size_t ndigits, int num)
{
    struct rep r;
    static char ret[MAX+1];
    size_t i;
    convert(num, ndigits, &r);
    if (r.n == MAX)
        return NULL;
    for (i=r.n; i; --i)
        ret[r.n-i] = digits[r.digits[i-1]];
    ret[r.n-i] = 0;
    return ret;
}

Then, we can write our driver program:

int main(void)
{
    const char digits[] = {'x','y','z'};
    size_t ndigits = sizeof digits / sizeof digits[0];
    int i;
    for (i=0; i < 100; i++) {
        char *data = next(digits, ndigits, i);
        if (data)
            printf("%s\n", data);
        else
            fprintf(stderr, "%d, error converting\n", i);
    }
    return 0;
}

I have written convert and next above so that they're independent of each other (apart from the obvious simplification that I'm using reversed representations). This makes it easy to use them in other programs.

Answer 4

Looks like instead of get_next you need to overload the operator++. This leads to the next derivation which is that this thing should be a separate object.

I would convert the "digits" into decimal, then operate on them, then convert them back.