Я хотел бы многократно производить быструю случайную перетасовку с минимальным смещением.
Известно, что тасование Фишера-Ятса является беспристрастным, если основной генератор случайных чисел (ГСЧ) беспристрастен.
To shuffle an array a of n elements:
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
Но что, если ГСЧ смещен (но быстро)?
Предположим, я хочу произвести множество случайных перестановок массива из 25 элементов. Если я использую алгоритм Фишера-Йейтса со смещенным ГСЧ, то моя перестановка будет смещена, но я считаю, что это предполагает, что массив из 25 элементов начинается с того же состояния перед каждым применением алгоритма перемешивания. Одна проблема, например, заключается в том, что если ГСЧ имеет только период 2 ^ 32 ~ 10 ^ 9, мы не можем произвести все возможные перестановки из 25 элементов, потому что это 25! ~ 10 ^ 25 перестановок.
Мой общий вопрос: если я оставлю перемешанные элементы перемешанными перед запуском каждого нового приложения перемешивания Фишера-Йейтса, уменьшит ли это смещение и / или позволит ли алгоритму производить каждую перестановку?
Я предполагаю, что это, как правило, дает лучшие результаты, но похоже, что если бы в повторно перетасованном массиве было несколько элементов, связанных с базовым ГСЧ, перестановки могли бы повторяться чаще, чем ожидалось.
Кто-нибудь знает какое-либо исследование, посвященное этому вопросу?
В качестве подвопроса: что, если мне нужны только повторяющиеся перестановки 5 из 25 элементов в массиве, поэтому я использую алгоритм Фишера-Йейтса для выбора 5 элементов и остановки перед выполнением полного перемешивания? (Я использую 5 элементов на конце массива, который поменяли местами.) Затем я начинаю заново, используя предыдущий частично перемешанный массив из 25 элементов, чтобы выбрать другую перестановку 5. Опять же, похоже, что это было бы лучше, чем начинать с исходный массив из 25 элементов, если базовый ГСЧ имел смещение. Есть мысли по этому поводу?
Я думаю, что было бы легче протестировать случай частичного перемешивания, поскольку существует только 6 375 600 возможных перестановок 5 из 25 элементов, поэтому есть ли какие-нибудь простые тесты для проверки смещений?
