Какая хорошая однопроходная псевдослучайная перетасовка?

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 карты.

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

Ответы

Ответ 1

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

ForEach card in batch:
    gap = random(deck.size() + 1)  # choose a gap between cards, before first, or after last.
    deck.insertAt(gap,card)

Распределение

Распределение случайности равномерное, а порядок колоды остается неизменным, поэтому он все равно однородный. Я думаю, что результат должен быть однородным. (Моя статистика слишком ржавая, чтобы быть уверенным).

Время

Предполагая, что insertAt является O (1) не O (N) - который зависит от реализации колоды - вся процедура - O (размер партии) - это лучшее, на что вы можете надеяться, потому что вам приходится обрабатывать каждую карту.