Возвращая случайное целое число от интервала на основе последнего результата и семени

Question

Предположим, у нас есть интервал целых чисел [A, B].Я хотел бы иметь функцию, которая возвращает случайные члены из интервала, без повторений.Как только все члены в интервале изучены, функция начнет снова возвращать одну и ту же первую случайную последовательность в том же порядке.

Пример: a= 1, b= 5

3, 1, 4, 5, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 2, ...

.

Это было бы легко достичь, путем перемещения массива всех элементов между A и B и повторяя его после завершения массива.Однако это займет слишком много места памяти, и это не подходит для моего случая (у меня могут быть миллионы элементов).

вместо этого, функция, которую я хотел бы иметь более или менее, подобную этой:

f(a, b, n, seed) -> n+1

.

Где:

a - start of interval
b - end of interval
n - last element returned from list
seed - self-explanatory
n+1 - next random element from list, calculated by using the seed and the last element returned (n)

.

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

Answer 1

Я предлагаю вам выбрать случайную перестановку на диапазоне $ [a, b] $ , т. Е. Функция бикторизации $ i= a $ ; На каждом шаге вывод $ \ pi (i) $ а затем увеличение $ i $ (обертывание вокруг что $ b + 1 $ становится $ a $ ).

Есть стандартные методы для генерации такой случайной перестановки в криптографической литературе: посмотрите на защиту от формата шифрования. Семя является криптографическим ключом. Вы сможете вычислить $ \ pi (i) $ в $ o (1) $ time и $ O (1) $ space, поэтому это должно быть очень эффективным и избежать необходимости в большом количестве хранения.

Если вы наставите, что следующий вывод должен быть функцией предыдущего выхода, вы можете позволить $ G (I)= I + 1 $ (кроме < Spaness Class="Математический контейнер"> $ g (b)= a $ ), то пусть $ f (i)=pi ^ {- 1} (g (\ pi (i)) $ , где $ \ pi $ - это случайная перестановка, выбранная как указана выше. Это даст вам случайный цикл, который итерации Через элементы $ [a, b] $ в случайном порядке. Выходы - это последовательность $ f (A) , f (f (a)), f (f (f (a))), \ dots $ .