以不同的基数计数

Question

如果要计算超过 8 位，以 2 为基数，结果如下：

0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 1;
0 0 0 0 0 0 1 0;
.....
1 1 1 1 1 1 1 1;

但是，您如何制作一种基于不同基数对每个位进行计数的算法，例如：如果根据基数 5 计算最低有效位，而最高有效位以基数 2 计算，则结果应如下所示：

0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 1;
0 0 0 0 0 0 0 2;
0 0 0 0 0 0 0 3;
0 0 0 0 0 0 0 4;
1 0 0 0 0 0 0 0;
1 0 0 0 0 0 0 1;
1 0 0 0 0 0 0 2;
...
1 0 0 0 0 0 0 4;

你能给我生成这些向量的算法吗？

Answer 1

这个问题的一种算法是大多数学生通常在幼儿园学习的那种“波纹进位”加法，除了稍微修改。当您将两个数字相加时，您会逐个数字地进行：首先是个位，然后是十位，然后是百位，等等。如果您不得不写下大于 10 的数字（例如 7+8 =15)，然后你把它写下来减去 10，然后把 10“携带”到下一个地方，在那里你把它加起来（它变成 1）；这可能会在许多地方“波动”（例如 999+1=1000）。用这个算法反复加一，就可以一一计数了。

澄清我们的目标很重要：不同的地方有不同的基地意味着什么。如果您允许位置具有任意数字范围并代表任意数字，那么可能会发生一些不好的事情：一个数字可以用多种方式书写，和/或一些十进制数字不能书写。因此，我们将把自己限制在一个“理智”的方案中，如果一个地方i有一个基数b _i，这意味着有效数字是 0,1,2,..., b _i -1（像往常一样，就像十进制)，并且那个地方的数字代表b _i乘以右边所有底数的乘积 ( b _i-1 x b _i-2X ...）。例如，如果我们的基数是 [10,10,10]，那么数字的值将是 [1000,100,10,1]；如果我们的基数是 [5,10,5]，则数字的值将是 [250,50,5,1]

如何给一个数加1：

Increment the least-significant digit (LSD)
Perform ripple-carry as follows:
    Set the current place to the LSD
    Repeat as long as the current place exceeds its allowed max digit:
        Set the digit at the current place to 0
        Advance the current place one to the left
        Increment the number at the new place (now on the left)

重复上述算法，直到您拥有所需的所有数字。

Python：

from itertools import *

def multibaseCount(baseFunction):
    currentDigits = [0]
    while True:
        yield currentDigits[::-1]

        # add 1
        currentDigits[0] += 1

        # ripple-carry:
        for place,digit in enumerate(currentDigits):
            if currentDigits[place]>=baseFunction(place):    # if exceeds max digit
                currentDigits[place] = 0         # mod current digit by 10
                if place==len(currentDigits)-1:  # add new digit if doesn't exist
                    currentDigits += [0]
                currentDigits[place+1] += 1      # add 1 to next digit
            else:    # doesn't exceed max digit; don't need to carry any more
                break

演示，其中位置 n 的基数为 n+1：

>>> for digits in islice(multibaseCount(lambda n:n+1),30):
...     print( ''.join(map(str,digits)).zfill(5) )
... 
00000
00010
00100
00110
00200
00210
01000
01010
01100
01110
01200
01210
02000
02010
02100
02110
02200
02210
03000
03010
03100
03110
03200
03210
10000
10010
10100
10110
10200
10210