Генерация случайной последовательности целых чисел, отличающихся на 1 бит без повторов

Question

Мне нужно сгенерировать (псевдо) случайную последовательность из N битных целых чисел, где последовательные целые числа отличаются от предыдущих всего на 1 бит, и последовательность никогда не повторяется.Я знаю, что код Грея будет генерировать неповторяющиеся последовательности только с разницей в 1 бит, а LFSR будет генерировать неповторяющиеся случайные последовательности, но я не уверен, как объединить эти идеи для получения того, что я хочу.

Практически, N будет очень большим, скажем, 1000. Я хочу случайным образом выбрать это большое пространство из 2 ^ 1000 целых чисел, но мне нужно сгенерировать что-то вроде случайного блуждания, потому что рассматриваемое приложение может переключаться только с одного числа наследующий, переворачивая один бит.

Answer 1

Используйте любой алгоритм генератора случайных чисел для генерации целого числа от 1 до N (или от 0 до N-1 в зависимости от языка). Используйте результат, чтобы определить индекс бита для отражения.

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

Answer 2

Это заставляет меня думать о фракталах - следуя границе в множестве джулии или что-то в этом роде.

Если N равно 1000, используйте фрактальную битовую карту 2 ^ 500 x 2 ^ 500 (очевидно, не генерируйте ее заранее - вы можете получить каждый пиксель по требованию, и большинство не понадобится). Каждое перемещение пикселя на один пиксель вверх, вниз, влево или вправо следует за границей между пикселями, как простой алгоритм трассировки растрового изображения. До тех пор, пока вы начинаете с края растрового изображения, вы должны рано или поздно возвращаться к краю растрового изображения - после определенной «цветовой» границы всегда должна получаться замкнутая кривая без самопересечений, если вы смотрите на неограниченные версия этого фрактала.

Оси x и y растрового изображения, разумеется, потребуют координат с серым кодом - немного похоже на карты Карно увеличенного размера. Каждый шаг в трассировке (один пиксель вверх, вниз, влево или вправо) приравнивается к однобитовому изменению в одной координате растрового изображения и, следовательно, в одном бите результирующих значений при случайном обходе.

EDIT

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

 * | .
---+---
 . | *

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

I думаю, проблему можно устранить, сделав так, чтобы во фрактале было по крайней мере три цвета, и всегда оставляя один и тот же цвет одной конкретной стороне (относительно направления трассировки) границы. Однако может существовать условие «пока фрактал не слишком морщинистый».

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

Answer 3

Хотя алгоритм такой:

seed()
i = random(0, n)
repeat:
    i ^= >> (i % bitlen)
    yield i

… вернет случайную последовательность целых чисел, каждое из которых будет отличаться на 1 бит, для обратного отслеживания потребуется огромный массив для обеспечения уникальности чисел. Чем дальше, тем больше будет ваше время бега экспоненциально (?) С увеличением плотности вашего обратного следа, так как шанс попасть на новое и неповторяющееся число уменьшается с каждым числом в последовательности.

Чтобы уменьшить время и пространство, можно попытаться включить один из них:

Фильтр Блума

Используйте Фильтр Блума , чтобы резко уменьшить пространство (и время), необходимое для отслеживания уникальности.

Как и Фильтры Блума имеют недостаток в том, что время от времени производят ложные срабатывания с определенной частотой ошибочно обнаруженных повторов (sic!) (которые, таким образом, пропускаются) в вашей последовательности будет происходить.

В то время как использование Bloom Filter уменьшит пространство и время, которое ваше время работы будет по-прежнему увеличиваться в геометрической прогрессии (?)…

Кривая Гильберта

A Кривая Гильберта представляет неповторяющуюся (разновидность псевдослучайного) хождения по квадратичной плоскости (или в кубе) с каждым шагом, имеющим длину 1.
Используя Кривая Гильберта (при соответствующем распределении значений), можно полностью избавиться от необходимости возврата. Чтобы ваша последовательность могла получить начальное число, вы должны сгенерировать n (n - это размер вашего самолета / куба / гиперкуба) случайных чисел в диапазоне от 0 до s (s - это длина вашего самолета / куба). / стороны гиперкуба). Мало того, что Кривая Гильберта устранит необходимость в обратной трассировке, это также заставит секвенсор работать в O(1) на число (в отличие от использования обратной трассировки, что увеличит время выполнения экспоненциально (?) со временем…)
Чтобы заполнить вашу последовательность, вы должны перевернуть ваше n -мерное распределение случайными смещениями в каждом из n измерений.

---

Ps: Вы можете получить лучшие ответы здесь: CSTheory @ StackExchange (или нет, см. Комментарии)