Алгоритмы перемешивания: Fisher-Yates и его варианты

Fisher-Yates — золотой стандарт перемешивания массивов. Единственный корректный алгоритм для честной колоды карт.

Алгоритм Fisher-Yates (Durstenfeld)

for i from n−1 downto 1: j = random(0, i), swap(a[i], a[j]). Работает in-place за O(n). Каждая из n! перестановок имеет вероятность 1/n!. Единственный алгоритм с равномерным распределением всех перестановок.

Типичные ошибки

"Naive shuffle": for i in 0..n: swap(a[i], a[random(0,n)]) — даёт nⁿ последовательностей вместо n! равномерно. Bias особенно заметен для колод карт: некоторые расклады чаще других. Проверка: тест chi-square на распределение перестановок.

Требования к RNG

Для колоды 52 карт нужно 52! ≈ 2²²⁵ уникальных перестановок. PRNG с 32-битным seed даёт только 2³² перестановок — критически мало. Для покера и блэкджека нужен минимум 226-битный seed. Используйте CSPRNG.

Применение

Live-покер: тасование колоды перед каждой раздачей. Cardpicker в баккаре. Order randomization в pick-bonus (символы под фишками). Провабли-фейр реализация: детерминированный shuffle с публичным seed для верификации игроком.