Я хотел бы многократно производить быстрые случайные тасования с минимальным смещением.
Известно, что тасование Фишера-Йейтса не смещено, пока основной генератор случайных чисел (ГСЧ) ) несмещен.
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 элементов, Итак, есть ли какие-нибудь простые тесты для проверки смещений?