#random #shuffle #playlist
#Случайный #перемешивание #список воспроизведения
Вопрос:
Мне нужно перетасовать около 1000 строк вида «название — исполнитель», где некоторые названия повторяются (скажем, «Тихая ночь»), а некоторые исполнители повторяются (скажем, «Бинг Кросби»). Ни одна из комбинаций «название — исполнитель» не повторяется, и никаких дополнительных дефисов нет.
Я хотел бы получить список с как можно большим пространством между одинаковыми названиями и между одинаковыми исполнителями.
Я склоняюсь к тому, чтобы просто случайным образом перетасовывать весь список много тысяч раз и сохранять тот, который имеет наибольшее расстояние между ближайшей парой идентичных повторов.
Еще одна грубая сила: перемешайте (только один раз), затем повторите множество раз: найдите ближайшую пару и замените одну из них на другую случайную точку.
Одно кажется лучше другого? Что-нибудь поумнее, но все равно простое?
Огромное спасибо!
Комментарии:
1. «Я бы хотел, чтобы в итоге получился список с как можно большим промежутком между одинаковыми названиями и между одинаковыми исполнителями». Тогда это не было бы случайностью. Это заставило бы такие вещи группироваться в начале и конце списка. В качестве первого шага вам нужно решить, что именно вы хотите сделать. Моя догадка заключается в том, что у вас есть приблизительное представление, но для разработки алгоритма вам нужен конкретный критерий.
2. Третья возможность заключается в том, чтобы указать минимально допустимый интервал между такими повторами и случайным образом перемешивать, пока не будет достигнут этот порог. Камнем преткновения является то, что для некоторых комбинаций параметров это может быть либо невозможно, либо исчезающе маловероятно. В качестве предохранительного клапана установите тайм-аут, который в этом случае возвращает ваш первый вариант. Это естественный вопрос, который встает перед каждым, кто хочет написать удобную для человека функцию перемешивания для списков воспроизведения. Некоторые другие идеи см. В Этом вопросе (из Software Engineering ).
3. У вас мало примеров строк для вставки? Может быть 50-100 строк?
4. @JohnColeman: Вы должны публиковать свои комментарии в качестве ответа и, возможно, процитировать часть вопроса, на который вы ссылались. В общем, ответы на вопросы не должны отображаться в виде комментариев.
Ответ №1:
Идеальный Джон Коулман! Спасибо! Идентичный вопрос с предложениями здесь: https://softwareengineering.stackexchange.com/q/194480/233981
———— РЕДАКТИРОВАТЬ ————
Я не мог быть более доволен своим результатом!
В отличие от op (me) я игнорировал повторяющихся исполнителей. Два «Бинга Кросби» подряд действительно не имеют значения по сравнению с двумя «Белыми рождественскими».
Я взял самую популярную песню и равномерно распределил ее по незаселенному массиву. Затем вторая по популярности песня и сделал то же самое, увеличив количество коллизий до # 1. Повторите весь список, включая песни с 0 повторами, заполняющими последние пустые ячейки.
Таким образом, каждый 34-й трек — это (другой) «Silent Night» (# 1), который невозможно обнаружить как слушатель. Каждый 46-й трек — «White Christmas» (# 2, начинающийся в другом месте, с коллизиями, увеличенными до 1 после «Silent Night»)….
Для слушателя это не может быть более случайным и не имеет ошибок / повторов, которые я всегда получаю с помощью rand() , noise() и всех их сестер. 😉
Что-то вроде этого:
populate the result list with null's
for each unique title, sorted from greatest # of repeats -> fewest # of repeats {
perfectSpacing = list.size() div (number of times this title repeats)
i = random(list.size()) // random starting location for this title
for each unique version of this title {
while (list[i] != null) // bump past populated slots, wrapping around
i = (i 1) % list.size()
list[i] = current version of the current title
i = (i perfectSpacing) % list.size()
// jump the ideal distance for the next version of this title
}
}
Хотя «столкновение с прошлыми коллизиями» создает риск обтекания и создания повторяющегося повтора, количество повторов в наборе данных слишком мало, чтобы допустить это. Почти половина из них вообще не повторяется, а для тех, которые повторяются, кривая от «много повторов» до «всего несколько повторов» очень быстро ухудшается.
Надеюсь, это когда-нибудь кому-нибудь поможет!