Создать случайную перестановку 1..N в постоянном пространстве

Я пытаюсь перечислить случайную перестановку чисел 1..N в фиксированном пространстве. Это означает, что я не могу хранить все числа в списке. Причина этого в том, что N может быть очень большим, больше, чем доступная память. Я все еще хочу иметь возможность пройти через такую ​​перестановку чисел по одному, посещая каждое число ровно один раз.

Я знаю, что это можно сделать наверняка. N: Многие генераторы случайных чисел циклически проходят через все свое пространство состояний случайным образом, но полностью. Хороший генератор случайных чисел с размером состояния 32 бита выдаст перестановку чисел 0..(2^32)-1. Каждое число ровно один раз.

Я хочу, чтобы N было вообще любым числом и не ограничивалось, например, степенями двойки. Есть ли алгоритм для этого?

21
задан usr 7 April 2012 в 13:03
поделиться