Самый эффективный способ подсчета диапазона чисел без смещения?

Question

Я хочу напечатать диапазон чисел в STDOUT.Но вместо того, чтобы считать от 0, 1, 2 ... N-1, N, я хочу повторить, используя поиск в ширину.Я хочу сделать это с наименьшим количеством / наименее интенсивными инструкциями (то есть без разветвления).

Например, допустим, диапазон составляет [1, 128].Я хочу посчитать так:

64
32
96
16
87
...
128
1

Честно говоря, мне все равно, сначала ширина или глубина или что-то еще.Мне просто нужен алгоритм подсчета, который равномерно покрывает числовую линию , чтобы, если бы числовая линия была качелей, она была бы сбалансирована с начала до конца алгоритма.

Инет, это не домашняя работа: -P

РЕДАКТИРОВАТЬ: Ищите что-то, что O (n) и не полагается на сохранение всего списка.

Answer 1

Сортировка чисел с использованием обращенных битов в качестве ключа.

Этот код Python демонстрирует концепцию:

>>> sorted(range(1,128), key=lambda x: ('{:08b}'.format(x))[::-1])
[64, 32, 96, 16, 80, 48, 112, 8, 72, 40, 104, 24, 88, 56, 120, 4, 68, 36, 100, 20, 84, 52, 116, 12, 76, 44, 108, 28, 92, 60, 124, 2, 66, 34, 98, 18, 82, 50, 114, 10, 74, 42, 106, 26, 90, 58, 122, 6, 70, 38, 102, 22, 86, 54, 118, 14, 78, 46, 110, 30, 94, 62, 126, 1, 65, 33, 97, 17, 81, 49, 113, 9, 73, 41, 105, 25, 89, 57, 121, 5, 69, 37, 101, 21, 85, 53, 117, 13, 77, 45, 109, 29, 93, 61, 125, 3, 67, 35, 99, 19, 83, 51, 115, 11, 75, 43, 107, 27, 91, 59, 123, 7, 71, 39, 103, 23, 87, 55, 119, 15, 79, 47, 111, 31, 95, 63, 127]

Просмотр битовых комбинаций для каждого числа показывает, как / почему он работает:

>>> '{:08b}'.format(64)
'01000000'
>>> '{:08b}'.format(32)
'00100000'
>>> '{:08b}'.format(96)
'01100000'

Обратите внимание, что процесс также можно выполнять на лету, не требуя сортировки:

* * 1010

В C изменение битов - тривиальное упражнение:

long reverse(long x) {
    long result = 0:
    int i;

    for (i=0 ; i<32 ; i++) {
        result <<= 1;
        result |= x & 1;
        x >>= 1;
    }
    return result;
}

Answer 2

Хорошо, я думаю это выполнимо при минимальном хранении данных.Это только для полностью сбалансированных, залитых деревьев.Расширить его до еще одного элемента легко (просто распечатайте лишний последний ...), но больше об этом потребуется еще немного подумать.Кроме того, если ваш диапазон не 1 ... N, а M ... N, достаточно просто добавить M-1 ко всему.

1. Нижний ряд дерева - 1, 1 + 2, 1 + 4, 1 + 6 и т. Д.
2. Второй-нижний ряд дерева - 2, 2 + 4, 2 + 8 и т. Д.
3. Третий-изнижний ряд дерева 4, 4 + 8, 4 + 16 и т. д.
4. и т. д.

Итак, для дерева 1 .. (N-1),где N - степень двойки, мы можем сначала вычислить высоту дерева, используя log₂ (N).Для удобства пусть n = N-1.Пример дерева: N = 16:

Первая строка (корень) дерева ((n-1) / 2) +1.Назовите этот ряд 0. Так что вы можете пойти дальше и напечатать это.Первый элемент следующей строки (строка 1) является половиной первого элемента предыдущей строки.И удобно, приращение является первым значением предыдущего ряда.Таким образом, для N = 16, первый элемент строки 2 = 4. Вы можете напечатать это.Следующий элемент 4 + 8 = 12, который вы можете распечатать.Поскольку строка содержит 2 * элемента rownum, теперь вы закончили со строкой 0 (2 ** 1 = 2). Следующая строка начинается с половины того, что сделала предыдущая строка, например, 2/2 = 2. Она имеет 2 **2 = 4 элемента с шагом 4. Итак, 2, 6, 10, 14.

               8

      4                12

  2       6       10         14
1   3   5   7   9   11    13    15

Теперь, если вы хотите 1… 16, вы можете просто добавить дополнительный элемент в правом нижнем углу., так что вы должны вывести его последним.

Конечно, вместо того, чтобы постоянно вызывать pow (), вы просто умножаете на 2 (что компилятор, при необходимости, превратится в битовый сдвиг)определить, сколько узлов этого уровня.Конечно, еще будут ветки для проверки петель.

Я должен предупредить вас, что сегодня мне еще не хватило чая, так что это может быть явно глупо.Но это похоже на работу.По крайней мере, в моей голове: -D

Answer 3

Может быть, вы хотите Серый код

или простой полный период генератор псевдослучайных чисел ограниченный вашим диапазоном