algorithm - 不重复相邻数字的数字序列

Question

我想获得一个数字序列，在给定基数的情况下，该序列不包含某个基数中重复的后续数字。我用一个例子来解释自己:在基数 10 中，序列将是 0、1、...、10、12、...21、23、...等。没有像 11 这样的数字, 125568, 220, 等等

或者，等价地，我想告诉你，基数 6 中的数字 521 包含一个重复的重复项(基数 10 中的 521 = 基数 6 中的 2225)。

有没有一种方法可以迭代十进制数，使其在给定基数中的表示不包含任何重复项？我的意思是，在基数 6 中，20 之后的(十进制)数字是 22(因为 20 是 32，而 22 是 34)。

当然，所有这些都没有对给定基数中的索引进行转换并检查是否有重复数字。

[编辑] 有一种方法可以判断一个十进制数(可以说是索引)在某个基数中是否有重复的连续数字，以便我可以在生成序列时跳过它？

Answer 1

生成一系列数字

要检查单个数字是否包含特定基数中的相等相邻数字，请在下面进一步查看我的初始答案。如果要生成在某个基数中相邻数字不相等的数字范围，最好将检查构建到生成器中，而不是检查所有数字。

以下代码示例创建了一个表格，其中包含特定基数中每个数字的值，并将数字零创建为数字数组。每个具有相同基数的后续调用都会增加数字，同时跳过相等的相邻数字。

function next(base, reset) {
    // If this is the first call, or if the base has been changed, a
    // new table with the values of digits in this base is generated.
    if (base !== next.base) {
        initialize_table();
        reset = true;
    }
    // If reset flag is set, re-initialize array of digits to zeros.
    if (reset) {
        initialize_digits();
        return 0;
    }
    increment_digits();
    return calculate_value();

    // The distinct parts of the algorithm have been split into 
    // seperate functions for clarity; for speed, integrate them.
    function initialize_table() {
        // The base, digit value table and array of digits are stored
        // as static variables, to be re-used between function calls.
        next.base = base;
        next.table = [];
        // Set a maximum for the values in the table (here it's 32-bit
        // unsigned integers); this determines the size of the table.
        // No overflow checking is done; add this if required.
        for (var pos = 0, val = 1, step = 1; val < 4294967296; pos++){
            next.table[pos] = [0];
            for (var digit = 1; digit < base; digit++, val += step) {
                next.table[pos][digit] = val;
            }
            step = val;
        }
    }
    function initialize_digits() {
        next.digit = [];
        for (var pos = 0; pos < next.table.length; pos++) {
            next.digit[pos] = 0;
        }
    }
    function increment_digits() {
        // Find the lowest digit that can be incremented.
        // No overflow checking is done; add if required.
        var pos = 0;
        while (next.digit[pos] == base-1 ||
               next.digit[pos] == base-2 &&
               next.digit[pos+1] == base-1) {
            ++pos;
        }
        // Add 1, or 2 if adding 1 would equal the next digit.
        while (++next.digit[pos] == next.digit[pos+1]);
        // Set the lower digits to 0 or 1 alternatingly.
        for (pos-- ; pos >= 0; pos--) {
            next.digit[pos] = (next.digit[pos+1] == 0) ? 1 : 0;
        }
    }
    function calculate_value() {
        // Look up value for each digit in the table and add up.
        var val = 0;
        for (pos = 0; pos < next.digit.length; pos++) {
            val += next.table[pos][next.digit[pos]];
        }
        return val;
    }
}

for (var b = 9; b > 1; b--) {
    document.write(b + " &rarr; ");
    for (var i = 0; i < 25; i++)
        document.write(next(b) + " ");
    document.write("...<br>");
}

单号校验

最有效的方法(特别是如果你想检查具有相同基数的多个数字)是首先制作一个表，其中包含该基数中每个数字的值，然后根据该表从高到低检查数字.这样你就可以避免除法和取模，它们在计算上是昂贵的，而且你可以在找到两个相同的数字后立即返回，而不必进行完整的基本转换。

---

假设基数是 6，数字是 16 位无符号整数，最大值为 65535，那么表格将是:

position: 0     1     2     3     4     5     6
digit:
  0  ->   0     0     0     0     0     0     0
  1  ->   1     6    36   216  1296  7776 46656
  2  ->   2    12    72   432  2592 15552     -
  3  ->   3    18   108   648  3888 23328     -
  4  ->   4    24   144   864  5184 31104     -
  5  ->   5    30   180  1080  6480 38880     -

假设我们正在检查数字 49876；我们首先检查位置 6 的数字值:

49876 >= 46656 ? yes
-> digit at position 6 is 1

然后我们用49876减去46656得到3220，然后继续检查第5位数字的值:

3220 >= 38880 ? no
3220 >= 31104 ? no
3220 >= 23328 ? no
3220 >= 15552 ? no
3220 >=  7776 ? no
-> digit at position 5 is 0

这个数字与前一个不同。我们不从数字中减去任何东西，因为数字是零；然后我们继续处理第 4 位数字的值:

3220 >= 6480 ? no
3220 >= 5184 ? no
3220 >= 3888 ? no
3220 >= 2592 ? yes
-> digit at position 4 is 2

这个数字也和前一个不同。我们用 3220 减去 2592 得到 628；然后我们继续处理位置 3 的数字值:

628 >= 1080 ? no
628 >=  864 ? no
628 >=  648 ? no
628 >=  432 ? yes
-> digit at position 3 is 2

这与前面的数字相同，因此我们知道该数字在 6 进制中有两个相同的相邻数字。

---

该表可以仅使用加法构建，而且它相对较小(最多 16×16 = 256 个元素用于检查 base-16 中的 64 位整数)并且可以重复用于检查同一个中的多个数字根据。检查数字仅通过比较和减法即可完成；绝对没有模数、除法甚至乘法，所以它应该非常快。

如果数字包含相同的相邻数字，算法可以在检查所有数字之前返回答案。如果没有相同的相邻数字，则检查所有数字，这实际上是一个完整的碱基转换；但至少它是有效地完成的。