将索引从自定义字母表转换为序列

Question

我想生成一个函数，它接受一个整数 x 和一个字符数组，并返回一个字符串 x 进入序列。

例如，考虑字母表 'abc'，它会产生字符串 a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab... 如果传入索引 0，我希望输出为“a”；同样，如果传入索引 34，我希望输出“cbb”。

对于字母表“0123456789”，我希望字符串为 0、1、2、3、4、5、6、7、8、9、00、01、02、03、04、05、06、07， 08、09、10、11...

到目前为止，我已经写了以下内容，但我卡在了行为偏离的情况 21-23、33-35、45-47 上，我已经盯着它看了好几个小时了，没有模式跳跃在我面前(关于字母大小和索引)。起初我没有注意到这个问题，使用了更大的字母表，直到它在我的程序中进一步产生了更大的问题。

我不会假装下面的代码是优雅的，遵循良好的实践，也没有优化 - 在这个阶段我真的只是想了解这个模式的正确实现并且一直在改变所有地方的东西尝试解决问题。如果变量名称令人困惑，请提前致歉。另外，这是一个常见的模式/问题吗？我曾尝试搜索类似的算法，但无法找到任何符合我想到的术语的算法。

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

你在那里尝试做的事情看起来像是基本转换，但实际上略有不同。任何基数中的任何数字都可以被认为好像它们在表示的数字后面有无限多个前面的零(或该基数上的最低有效数字)。这在你的情况下是不正确的。

在您的情况下，您非常重视您所代表的数字的位数，这使得为它们编制索引稍微复杂一些。有了数学中的基数，就可以很容易地计算出代表数字在任何基数 b 中的索引；也就是说，rank 乘以 base 的总和为每个数字的 order 次方。在您的情况下，索引建立了一个额外的 sum_{k = 1}^{amount.of.digits.on.our.number - 1} base^k。如果我们从索引中减去该加法，我们的任务就会变得相当简单。

可以使用您的 sumsqr 函数计算该加法。

在这里，我稍微更改了您的代码，并在我所做的更改处添加了注释，这能够解决许多问题，就像您期望的那样:

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

我不确定您要对我注释掉的部分做什么。我的猜测是您试图将 divisor 增加我之前谈到的差异量，而不是减少 index 或 remainder按这个数额。

希望这对您有所帮助。