Последовательность чисел без повторения соседних цифр

Создание диапазона чисел

Чтобы проверить, содержит ли одно число одинаковые соседние цифры в определенной базе, посмотрите мой первоначальный ответ ниже. Если вы хотите сгенерировать диапазон чисел, у которых нет одинаковых соседних цифр в определенном основании, лучше встроить проверку в генератор, а не проверять все числа.

В следующем примере кода создается таблица значений каждой цифры в определенном основании и создается число ноль в виде массива цифр. Каждый последующий вызов с той же базой будет увеличивать число, пропуская при этом равные соседние цифры.

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

Затем мы вычитаем 46656 из 49876, чтобы получить 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.

Таблицу можно построить, используя только сложение, и она относительно мала (до 1616 = 256 элементов для проверки 64-битных целых чисел по основанию 16), и ее можно повторно использовать для проверки нескольких чисел по одному и тому же основанию. Проверка числа выполняется только с помощью сравнений и вычитаний; там абсолютно нет модуля, деления или даже умножения, так что это должно быть очень быстро.

Если номер содержит одинаковые соседние цифры, алгоритм может вернуть ответ до проверки всех цифр. Если нет одинаковых соседних цифр, проверяются все цифры, что фактически представляет собой полное базовое преобразование; но по крайней мере это сделано эффективно.

Генератор рекурсивных итераций по цифрам устанавливает результирующий массив, а отслеживание цифр за цифрой дает естественный порядок чисел.

Генератор — это класс с членами класса:

int length;
int curVal[10];
boolean digits[10];

Здесь curVal содержит частично готовое число.

Нижний индекс соответствует позиции старшего разряда, а pos — это индекс, начинающийся с 0 и отсчитывающий от старшего к младшему разряду.

И digits — это набор (или логический массив, если хотите), чтобы отслеживать используемые цифры.

Прототип функции драйвера генератора выглядит так:

void generate(int pos)

Внутри вы делаете простой цикл от 0 до 9, и если цифра не входит в набор цифр, вставьте ее, добавьте в curVal[pos] и вызовите generate(pos+1). После возврата удалите цифру cur из набора и curVal.

Как только вы заполните последнюю цифру, распечатайте/поставьте номер в очередь для вывода потока/очереди/списка.

Вместо или в дополнение к curVal вы можете отслеживать двоичное представление. Предварительно рассчитайте 10 ^ i и добавьте precalc[length-pos-1]*digit к двоичному значению каждый раз, когда вы помещаете цифру в curVal, и вычтите, если вы вернете ее обратно.

Также вам нужно обрабатывать первую цифру отдельно, так как самая старшая цифра не может быть 0. Естественно, это можно сделать внутри основного цикла по длине с правильным

Это самое простое решение, которое я могу себе представить:

 private boolean check(long t, long base) {
    long x = -1;
    long y;
    while (t > 0) {
      y = t % base;
      if (y == x) {
        return false;
      }
      x = y;
      t = t / base;
    }
    return true;
  }