У меня есть список n элементов. Я хочу, чтобы алгоритм позволял мне выбирать потенциально бесконечную последовательность элементов из этой коллекции наугад, но с несколькими ограничениями:
- После того, как элемент был выбран, он не должен появляться снова в следующих нескольких элементах (скажем, в следующих m пунктах, где m явно строго < n)
- вам не нужно слишком долго ждать появления какого-либо элемента - элементы должны появляться в среднем после каждого выбора n
- последовательность должна быть нециклической
В принципе, я хочу, чтобы алгоритм генерировал плейлист для MP3-плеера с включенным "перетасовкой" и "повторением", который гарантирует, что он не воспроизводит ту же самую песню слишком близко к себе и гарантирует, что она воспроизводит все ваши песни равномерно, без видимых шаблонов.
Эти ограничения устраняют два очевидных решения из утверждения:
- Мы не можем просто выбрать rnd (n) в качестве индекса для следующего элемента, потому что это не гарантирует повторения; также может потребоваться много времени, чтобы выбрать некоторые элементы.
- Мы не можем просто предварительно перетасовать список с помощью Shuffle Fisher-Yates и повторять его несколько раз, перетаскивая его каждый раз, когда мы достигаем конца; в то время как это гарантирует, что товары появятся максимум после 2n-1 picks, это не полностью предотвратит повторение элемента.
Наивное решение может заключаться в том, чтобы выбирать случайным образом, но отклонять выборки, если они произошли в последних m выборках; это означает сохранить список из предыдущих выборов и каждый раз проверять каждый выбор на этот список, что делает алгоритм недетерминированным и медленным одновременно - проигрывает. Если я не пропущу что-то очевидное.
Итак, у меня есть алгоритм, который я использую сейчас, и я немного недоволен. Я получил его по аналогии с колодой карт, где у меня есть ничьи и свалка. Я начинаю с полного списка, перетасовывая, в стопку ничьей, сброс пустой пустой. Следующий элемент считывается с верхней части стопки ниши, а затем помещается в кучу сброса. Как только куча сбрасывания достигнет определенного размера (м пунктов), я перетасовываю его и перемещаю его на дно нитки.
Это соответствует требованию, но этот перетасовка один раз, когда меня выбирает, меня беспокоит. Он O (1) обычно, но O (m) один раз в m. Это в среднем равно постоянному времени, но должно быть более чистое решение, которое в случайном порядке перемещает выбросы.
Мне кажется, что это такая простая, общая и общая проблема, у нее должен быть один из этих двухствольных алгоритмов, таких как Fisher-Yates или Boyer-Moore. Но мой google-fu явно не силен, так как мне еще предстоит найти набор терминов, которые обнаруживают неизбежную бумагу 1973 ACM, которая, вероятно, объясняет, как это сделать в O (1) раз, и почему мой алгоритм глубоко испорчен в некотором роде.