Convert index to sequence from custom alphabet

Question

I would like to produce a function which takes an integer x and char array in, and returns a string x steps into the sequence.

For example, consider the alphabet 'abc', which would produce the strings a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab... If the index 0 was passed in, I would expect the output to be 'a'; likewise, if the index 34 was passed in, I would expect the output 'cbb'.

For the alphabet '0123456789' I would expect the strings 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11...

I have written the following thus far, but am getting stuck on cases 21-23, 33-35, 45-47 where the behaviour deviates and I've been staring at this for a number of hours now without a pattern jumping out at me (with respect to the alphabet size and index). At first I didn't notice the issue, using a larger sized alphabet until it created bigger issues further in my program.

I'm not going to pretend the code below is in anyway elegant, following good practice, nor optimised - at this stage I really just want to understand the correct implementation of this pattern and have been changing things all over the place to attempt to resolve the issue. Apologies in advance if the variable names are confusing. Also, is this a common pattern/issue? I have tried to search for similar algorithms but have been unable to find anything with the terms that come to mind.

unsigned long power(int num, int exp)
{
    int i;
    unsigned long ret = num;

    if (exp == 0) return 1;

    for (i = 1; i < exp; i++)
    {
        ret *= num;
    }

    return ret;
}

unsigned long sumsqr(int base, int exp)
{
    unsigned long sum;

    for (sum = 0; exp > 0; exp--)
    {
        sum += power(base, exp);
    }

    return sum;
}

char * generateStringT(unsigned long index, char * charmap)
{
    unsigned long scaler;
    unsigned long remainder;
    unsigned long divisor;
    int base;
    int exponent;
    int factor;  
    char * buffer;
    char * string;
    int i;

    buffer = malloc(sizeof(char) * 100);
    i = 0;

    base = strlen(charmap);

    exponent = 0;
    divisor = 0;
    remainder = index;

    while(sumsqr(base, exponent) <= index)
    {
        exponent++;
    }
    exponent--;

    factor = exponent;

    while(factor >= 0)
    {
        divisor = power(base, factor);
        if ((factor > 1) && (exponent > 0))
        divisor += power(base, factor-1);

        scaler = remainder/divisor;

        remainder = remainder - scaler * divisor;
        printf("%lu,", scaler);

        if ((factor == exponent) && (exponent > 0)) scaler--;
        buffer[i++] = charmap[scaler];

        factor--;
    }


    buffer[i++] = '\0';

    string = malloc((strlen(buffer) + 1) * sizeof(char));
    strcpy(string, buffer);
    free(buffer);

    return string;
}

Answer 1

What you are trying to do there looks like a base conversion, but actually is slightly different. Any number in any base can be thought as if they have infinitely many preceding zeros (or whatever the least significant digit is at that base) behind the represented number. This is not true in your case.

In your case, you lay importance to the amount of digits on the number you represent, making it slightly more complicated to index them. With bases in maths, it is easy to calculate the index of a represented number in any base b; that is, sum of the rank times the base raised to the power of order for each digit. In your case, the index builds up an additional sum_{k = 1}^{amount.of.digits.on.our.number - 1} base^k. If we subtract that addition from the index, our task becomes rather easy.

That addition can be calculated using your sumsqr function.

Here, I have changed your code just a little, with comments at where I've done changes, which is able to resolve many, just like you expect it to:

// added this
remainder -= sumsqr(base, exponent);

while (factor >= 0)
{
    divisor = power(base, factor);

    // commented this out
    // if ((factor > 1) && (exponent > 0))
    //  divisor += power(base, factor - 1);

    scaler = remainder/divisor;

    remainder = remainder - scaler * divisor;
    printf("%lu,", scaler);

    // commented this out
    // if ((factor == exponent) && (exponent > 0))
    //  scaler--;

    buffer[i++] = charmap[scaler];

    factor--;
}

I am not exactly sure what you were trying to do with the parts I've commented out. My guess is that you were trying to increase the divisor by that amount of difference I've talked previously, instead of decreasing the index or remainder by that amount.

Hope this helps in any way.

Answer 2

Not a fix (at a glance, your code uses a similar idea -- but more complicated!), but this is the code I used to convert an integer index to an a,b,c-format page number:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *number_alpha (char *dest, int value, char *base)
{
    char *ddest = dest, *startdest = dest, swop;

    if (value < 0)
    {
        value = -value;
        *dest = '-';
        startdest++;
        ddest++;
    }
    value++;
    do
    {
        *ddest = base[((value-1) % strlen(base))];
        ddest++;
        value = (value-1)/strlen(base);
    } while (value > 0);
    *ddest = 0;
    ddest--;
    while (ddest > startdest)
    {
        swop = *ddest;
        *ddest = *startdest;
        *startdest = swop;
        startdest++;
        ddest--;
    }
    return dest;
}

int main (int argc, char **argv)
{
    int number;
    char result[256];

    if (argc != 3)
    {
        printf ("usage: [number] [string]\n");
        return -1;
    }

    number = strtol (argv[1], NULL, 10);
    number_alpha (result, number, argv[2]);
    printf ("%d in 'base' %s yields %s\n", number, argv[2], result);

    return 0;
}

It is very similar to the common task 'convert an integer to decimal notation'. By removing the value++ and changing (value-1) twice to just value in number_alpha, you get a bog-standard Int-To-Ascii routine. This one is special because the "wrap" occurs at a different place: for a base of 0123456789, incrementing 9 shows 00, not 10.

Sample outputs:

0 in 'base' abc yields a
34 in 'base' abc yields cbb
34 in 'base' 0123456789 yields 24
-34 in 'base' abc yields -cbb
9 in 'base' 0123456789 yields 9
10 in 'base' 0123456789 yields 00

--

See Translate a column index into an Excel Column Name for a couple of implementations in other languages. They seem to focus on recursive solutions, where mine is linear (for better or worse).