algorithm - 在不同的基础上计数

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-2 x ...)。例如，如果我们的基数是 [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