Как вы можете пройти через целочисленный диапазон в непредсказуемом порядке?

Question

Как можно перебрать фиксированный диапазон целых чисел (скажем, 100000-999999) в трудно предсказуемом порядке?

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

т.е. Я хотел бы что-то более элегантное, чем просто А) выбрать случайное число, а затем Б) проверить, использовалось ли оно уже, и если да, вернитесь к шагу А по следующим причинам (если вы не можете убедить меня в обратном):

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

Answer 1

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

v = k * v + l mod m

где m - размер набора, k и l относительно простые числа m (я полагаю, этого достаточно, чтобы гарантировать, что он работает должным образом), а v - используемое значение. Выберите начальное значение более или менее случайным образом и перейдите оттуда.

Одним из преимуществ является то, что писать довольно быстро, предполагая, что вы можете избежать переполнения (либо ограничив k и m, либо используя арифметические процедуры произвольной точности).

Answer 2

Вы должны использовать регистр сдвига с линейной обратной связью . «Максимальная длина» LFSR будет поражать каждое число в диапазоне (2 ^ n -1), кроме 0. Вы можете сохранить первое число, чтобы вы знали, когда оно вернется к началу, или вы можете просто посчитать образцы. Проблема в том, что он является детерминированным, поэтому технически вы можете его предсказать, если знаете алгоритм. Кроме того, если задано любое число в последовательности, последовательность всегда будет одинаковой с этой точки.

Вы можете иметь список из множества алгоритмов LFSR и случайным образом выбрать один, прежде чем начать, чтобы он был менее предсказуемым от запуска к запуску. Но метод, который вы используете для выбора алгоритма, вероятно, тоже предсказуем ...

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

Answer 3

Если вам нужен криптографически безопасный способ сделать это, вы можете проверить мою статью о Криптографически безопасных перестановках с блочными шифрами . В двух словах, выберите блочный шифр, используйте технику, называемую сворачиванием XOR, чтобы уменьшить его до наименьшей степени 2, превышающей желаемый диапазон, а затем используйте следующую технику, чтобы генерировать только числа в желаемом диапазоне:

def permute(index, max):
  index = E(index)
  if index > max:
    return permute(index, max)

То есть просто «зашифруйте» любое сгенерированное вами число, выходящее за пределы желаемого диапазона. Объем работы, необходимый для генерации всей последовательности, ограничен количеством элементов в исходной последовательности. Худший случай для генерации одного элемента - 1 + unused_range, но это невероятно малая вероятность.

Вы можете применить это ко всему, что генерирует отображение 1: 1, конечно, не только к примеру блочного шифра. И если вы имеете дело с другим видом ГСЧ - например, LFSR, вместо повторного применения функции, просто пропустите этот элемент.

Answer 4

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

Answer 5

Используйте линейный конгруэнтный генератор случайных чисел и отбросьте все целые числа вне вашего диапазона.

Answer 6

Если порядок не должен быть действительно случайным (просто непредсказуемым) и если нам разрешено хранить диапазон значений небольшого размера (скажем, N), то:

1. Сохранить первые N значений в подсписке
2. Возвращать случайное значение из подсписка, пока, скажем, N / 2, значения не останутся
3. Добавьте еще N / 2 значения из основного списка в подсписок.
4. Повторяйте 2-3, пока все значения не будут сделаны.

Необходим шаг 2-3, иначе каждое N-е возвращаемое значение будет предсказуемым. Измените размер подсписка (N) и порог перезагрузки (N / 2), чтобы найти хороший компромисс между использованием памяти, частотой перезагрузки и «случайностью».

Answer 7

Создайте базу данных с номерами от 1 до N.

Пусть база данных сгенерирует случайное число для каждого из значений N.

Возвращает N значений, отсортированных по случайному числу.