Цель состоит в том, чтобы выбрать случайную песню из 1..N без повторений для N песен и иметь возможность перебирать вперед и назад, как в iPod. Я использовал хэш-таблицу для хранения случайных песен. Есть ли способ лучше?Эффективная реализация iPod-подобного алгоритма тасования?
Один из способов - использовать генератор псевдослучайных чисел на основе LCG для выбора песен. На каждом шаге песня n + 1 есть (a + b) Mod 2^N. убедитесь, что период LCG выше N. Итерация назад с использованием обратной линии LCG
Интересная идея. Как обеспечить, чтобы период был больше, чем N? – McDowells
ru.wikipedia.org/wiki/Linear_congruential_generator#cite_note-HullDobell-3 –
Разве это не дает явно неслучайную перестановку песен? – templatetypedef
Одним простым алгоритмом для этого было бы начать со списком всех N песен, а затем случайным образом перетасовать элементы массива с помощью алгоритма, такого как Fisher-Yates Shuffle. Как только вы это сделаете, у вас будет упорядочение всех песен в произвольном порядке и без дубликатов. Если вы отслеживаете свой текущий индекс в списке, вы можете реализовать следующий и предыдущий, просто перемещая вперед или назад в массиве.
Надеюсь, это поможет!
So O (NlogN) для перетасовки и O (N) пространства для поиска массива? – McDowells
@ McDowells - На самом деле, только O (n), чтобы выполнить тасование (Fisher-Yates запускается в O (n) времени), то только O (1) время поиска в массиве. Однако вам нужно использовать память O (n) для хранения перетасованного порядка. – templatetypedef
Смешайте массив индексов, менее дорогой в памяти. – arynaq
вы можете поделиться своим кодом? – pollirrata
Немного сложно написать это, не зная, что вы пишете! – GriffLab
Что вы имеете в виду с итерацией вперед и назад? – arynaq