Эффективный способ рандомизации массива - случайный код

Question

Мне задали этот вопрос в интервью, и я дал различные решения, но интервьюер не был убежден.Мне интересно найти решение.Пожалуйста, добавьте ваши взгляды:

Q: Напишите эффективную структуру данных для реализации случайного воспроизведения в iPod.Он должен воспроизводить все песни, каждый раз в различном случайном порядке, одну и ту же песню не следует повторять.(в основном O (n))

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

С уважением, Сетху

Answer 1

Вы хотите Фишера-Йейтса shuffle . Помните об ошибках реализации, упомянутых на этой странице, поскольку ваш принятый в настоящее время ответ не соответствует одному.

Answer 2

Поместите все песни в массив ... Для каждого элемента в массиве меняйте его случайной позицией.

Answer 3

Алгоритмы Нейта (отредактированные) и Брайана - это случайное перемешивание Фишера-Йейтса O (n), в то время как перетасовка с сортировкой - O (nlogn), но на практике может быть быстрее (http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Comparison_with_other_shuffling_algorithms). Неправильное перетасовывание песни может иметь незначительные последствия , но если вы пишете алгоритм тасования для онлайн-игры в покер, убедитесь, что вы знаете, что делаете (http://www.cigital.com/news/index.php?pg=art&artid=20).

Answer 4

Итак, первое решение с линейным временем, которое приходит на ум:

Вы можете составить связанный список всех песен, который займет около O (n) (учитывая, что вставки являются операциями с постоянным временем). Затем сгенерируйте случайное число, по модулю размера списка получите случайный индекс, удалите этот индекс и добавьте его в новый список (оба из которых являются операциями с постоянным временем).

Вставка для каждого O (n) + удаление для каждого O (n) + вторая вставка O (n). В целом это привело бы к линейному решению времени.

Редактировать : Я полностью забыл про просмотр списка. Таким образом, вместо этого вы можете сделать результат массивом фиксированной длины. Откройте заголовок связанного списка, назначьте ему случайный индекс и заполните массив.

Answer 5

То, что вы хотите, это Fisher-Yates Shuffle .Вот реализация в Java:

public void shuffle(Song[] songs) {
    Random r = new Random();
    for(int i = 0; i < songs.length - 1; i++) {
        int swap = i + r.nextInt(songs.length-1-i);
        T temp = songs[i];
        songs[i] = songs[swap];
        songs[swap] = temp;
    }
}
/* r.nextInt(max) returns integer 0 to max-1 inclusive */

Как это работает, он обрабатывает весь массив как шляпу и начинает вытягивать случайные элементы и выравнивать их в начале массива.Все элементы после i находятся «в корзине», все элементы до i перемешиваются.

Answer 6

Я новичок, позвольте мне сказать решение, которое приходит на ум, если что-то не так, пожалуйста, сообщите мне об этом.

Предположим, что песни хранятся в односвязном или двусвязном списке.Каждый раз, когда музыкальный проигрыватель открывается, выберите случайное число, меньшее, чем (любое желаемое вами число), чтобы принять k, и поменяйте местами каждые k узлов в списке, аналогичным образом сделайте это дважды или максимально трижды (как вы хотите), что будет принимать O2n) или O (3n) время, чтобы перемешать.наконец, есть указатель на последний узел списка.И каждый раз, когда прослушивается песня (посещается узел), удаляют узел и вставляют его рядом с последним узлом, что можно сделать за O (1) раз.Это продолжается до тех пор, пока музыкальный проигрыватель не закроется.

Спасибо, хочу знать правильность ответа.