Fisher-Yates shuffle дает хороший алгоритм для перетасовки массива A длины n за один проход:
For k = 1 to n
Pick a random integer j from k to n
Swap A[k] and A[j]
После одного прохода через этот алгоритм записи A происходят равномерно случайным образом.
Общим способом обработки этого алгоритма является выполнение следующих действий:
For k = 1 to n
Pick a random integer j from 1 to n
Swap A[k] and A[j]
Результирующее распределение из одного прохода через этот алгоритм не равномерно случайное, и есть хорошее обсуждение того, что есть на этом посту: Что вы получаете от этого сломанного случайного перетасовки?
Недавно я прочитал восхитительную статью Дьякониса, Фулмана и Холмса, озаглавленную "Анализ оборудования для перетасовки казино" , где авторы описывают физическую машину, выполняет следующую периодическую перетасовку:
For k = 1 to n
Pick a random integer j from 1 to 10
Randomly choose to place card k on the top or bottom of stack j
Вопрос, который адресован авторам, заключается в том, дает ли это случайное упорядочение после одного прохода. Ответ явно нет. Один из способов увидеть недостаток в этом перетасовке - начать с колоды карт с n/2 красными карточками поверх черных карт n/2. В результате колода после одного прохода будет иметь не более 10 комков красных карточек! Для n = 52*6 это не является случайным. Авторы также показывают, что оптимальная стратегия "угадать следующую карту" для некогда перетасованного будет в среднем правильно угадывать 9,5 карт, тогда как оптимальная стратегия для случайной колоды будет в среднем рассчитана только на 4,5 карты.
Есть ли другие интересные одноразовые тасования, которые достигают почти случайности и/или интересных распределений? Мне особенно интересны тасования, подобные последним, которые работают с партиями записей.
