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

Question

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

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

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

С уважением, Sethu

Answer 1

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

Answer 2

Ну, первое линейное время решение, которое приходит на ум:

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

Спасибо, Желаем знать правильность ответа.