Как реализовать случайное повторение тасования, но не слишком случайный
У меня есть список из n шт. Я хочу, чтобы алгоритм позволял мне выбирать потенциально бесконечную последовательность элементов из этой коллекции случайным образом, но с парой ограничений:
- как только элемент был выбран, он не должен ' выбор некоторых элементов также может занять много времени.
- Мы не можем просто предварительно перемешать список с помощью перемешивания Фишера-Йейтса и многократно перебирать его, перемешивая каждый раз, когда мы дойдем до конца; хотя это гарантирует, что предметы появятся максимум после 2n - 1 выбора, это не полностью предотвращает повторение предмета.
Наивным решением может быть выбор наугад, но отклонение выбора, если оно произошло в последних m выборах; это означает ведение списка m предыдущих выборов и проверку каждого выбора по этому списку каждый раз, что делает алгоритм недетерминированным и одновременно медленным - безнадежным. Если только я не упускаю что-то очевидное ...
Итак, у меня есть алгоритм, который я использую сейчас, который меня немного не устраивает. Я получил его по аналогии с колодой карт, где у меня есть стопка для вытягивания и стопка для сброса. Я начинаю с полного списка, перетасованного, в стопке взятия карты, стопка сброса пуста. Следующий предмет считывается сверху стопки и затем помещается в стопку сброса. Как только стопка сброса достигает определенного размера ( m предметов), я перемешиваю ее и перемещаю в конец колоды.
Это соответствует требованиям, но перемешивается каждые m меня беспокоит выбор. Обычно это O (1), но O (m) один раз в m. В среднем это составляет постоянное время, но должно быть более чистое решение, которое перетасовывает выбросы по мере их поступления.
Мне кажется, что это такая простая, общая и распространенная проблема, у нее должна быть одна из эти двуствольные алгоритмы, такие как Фишер-Йейтс или Бойер-Мур. Но мой гугл-фу явно не силен, как я ' Нам еще предстоит найти набор терминов, который определяет местонахождение неизбежной статьи ACM 1973 года, которая, вероятно, объясняет, как именно это сделать за время O (1), и почему мой алгоритм в некотором роде глубоко ошибочен.