Я ищу варианты псевдокодов для сортировки моих mp3-файлов таким образом, чтобы избежать повторения названий и исполнителей . Я слушаю эстрадных певцов - Фрэнка Синатру, Тони Беннетта, Эллу Фицджеральд и других, поющих старые стандарты. Каждый артист записывает множество одинаковых песен - Fly Me To The Moon, The Way You Look Tonight, Stardust и т. Д. Моя цель - расположить песни (или заказать плейлист) с максимальным пространством между исполнителями и названиями песен. Так что, если у меня 2000 песен и 20 песен Эллы, я бы хотел услышать ее только один раз из каждых 100 песен. Если 10 исполнителей поют Fly Me To The Moon, я бы хотел услышать это раз в 200 песен. Конечно, я хочу объединить эти два требования, чтобы создать мою «абсолютную случайность».
Я знаю, что это довольно широко открытый вопрос. Я еще не начал программировать его, поэтому я просто искал предложения о том, как выбрать подходящий подход. У меня действительно есть некоторые другие требования относительно равномерного распределения других атрибутов песни, но я не буду вдаваться в это здесь.
В качестве отправной точки я изменяю код, который нашел здесь, чтобы манипулировать mp3-файлами и читать теги ID3.
Я написал небольшое приложение, которое удовлетворяет мои потребности, используя ответ Парсифаля ниже. Я также написал следующий вопрос здесь . Спасибо за все отличные ответы!
источник
while (length(songs) > 0) { x := rand(); addElem(shuffle, songs[x]); remElem(songs, x); }
но вы говорите, что хотите "абсолютную случайность". Я не знаю, что вы действительно хотите с этим, даже читая вопрос ...Ответы:
Вы хотите запустить свою программу один раз и сгенерировать плейлист или выбрать следующую песню в прямом эфире?
Если последнее, то ответ прост:
Выбор песни становится следующей последовательностью шагов:
Есть несколько возможных проблем, но они должны иметь значение, только если вы делаете это как домашнее задание, а не как реальный проект.
источник
Я сделал что-то вроде этого, прежде чем использовать генератор (в C # - бесконечный цикл, в котором выполняется
yield
каждая итерация цикла). Каждая итерация просматривает пул песен (или что-то в этом роде) и отбрасывает те, которые были воспроизведены слишком недавно (или какие-то негативные критерии). Затем вы выбираете один из отфильтрованного списка и обновляете свое состояние. По мере того, как ваше состояние меняется (вы играете песни не из Синатры), критерии нарушаются, и ваши исключенные песни начинают повторно включаться.Конечно, есть угловые случаи, чтобы иметь дело с:
источник
Игнорируя выбросы вашего вопроса, которые поднимает Теластин, звучит так, будто у вас есть вариация в проблеме с рюкзаком . К счастью, это довольно хорошо документированный алгоритм.
Из Википедии
В этой статье перечислены некоторые потенциально важные варианты, а также дополнительный список проблем с рюкзаком.
Одним из вариантов проблемы ранца является многоцелевая задача ранца. Колонии муравьев алгоритм предлагается в качестве средства решения этой проблемы. Подход с использованием колонии муравьев может быть самым простым способом избежать сложнейших аспектов вашего вопроса.
Я также мог бы рассматривать вашу проблему как крайний вариант проблемы коммивояжера . Каждый город для посещения - это действительно песня, которую вы хотите сыграть, но я не уверен, как бы вы указали интервалы между исполнителями. Это предложение также связано с / может быть решено с помощью подхода колонии муравьев.
источник
Я работаю в предположении, что это «вот моя библиотека, запустите эту программу и сгенерируйте заказ для воспроизведения песен».
Это не было реализовано, и я не уверен, насколько хорошо он будет преобразовывать его перетасовку. Может быть, я слишком строг в фильтре, что привело бы (я полагаю) к предписанному порядку для остатка с учетом начального набора песен.
У одного есть
ideal_gap
хеш. Это рассчитывается по плотности песни с данным свойством (исполнитель, альбом, название). Если у вас есть 2000 песен и 20 из них исполнителем по имени Элла, тоideal_gap{'artist'}{"ella"}
будет 100.Имея эту информацию, можно также получить максимум значений ideal_gap. Давай называть это
max_gap
.Подумайте: имейте максимальное
ideal_gap
значение, чтобы песня, которую спели только два исполнителя, не позволяла другой песне воспроизводиться через 1000 песен позже, а также резко увеличивала значение max_gap, что приводило к многочисленным итерациям «back off, no song, back». нет, песен нет ".Изучение последних сыгранных композиций max_gap (это можно заполнить с предыдущего прогона, чтобы, если он закончится с песней Фрэнка Синатры «Fly Me To the Moon», следующий прогон не начнется случайно с той же самой песней), можно отфильтровать песни из библиотека, приводящая к набору песен-кандидатов. Песня будет только в песнях-кандидатах, если все ее промежутки меньше, чем
ideal_gap
для этих свойств.Из набора песен-кандидатов выберите одну наугад.
Рассмотрим: взвешивание набора так, чтобы песни, атрибуты с более высоким максимальным разрывом, были взвешены, чтобы быть более вероятными. Таким образом, в конце плейлиста не все песни с максимальным разрывом накапливаются.
Подумайте: вместо того, чтобы все три свойства были больше идеального разрыва, просто два из трех. Это может означать, что что-то может быть воспроизведено раньше, чем идеальный идеал, но увеличивает размер набора песен-кандидатов, а это означает, что у «выберите один наугад» больше возможностей.
Если нет песен, удовлетворяющих требованиям, отступите на
max_gap
1, и все ideal_gaps наn/max_gap
процентыn
- это количество раз, когда это было отменено. Таким образом, если есть значениеmax_gap
100, и оно было отменено 5 раз в этой итерации, идеальный интервал 100 будет скорректирован на временное значение 95, а идеальный интервал 20 скорректирован на временное значение 19. Повторите откат от пробел, пока не появится хотя бы одна песня-кандидат, а затем выберите ее, как указано выше.Учтите: имейте минимальный размер пула. Это увеличивает дисперсию, но может привести к тому, что песня будет воспроизведена раньше, чем идеальный промежуток, когда есть другая песня, которую можно воспроизвести.
источник
Это задание оптимизации, и довольно сложным , если вы ищете в оптимальном решении. К счастью, я верю, что это один из тех случаев, когда достаточно хорошо.
Первое, что нужно сделать, это установить математический критерий качества, то есть формулу, которая при заданной перестановке списка вернет одно число, описывающее, насколько хороша или плоха эта перестановка.
Предложение простой формулы, каждому критерию, который вы хотели бы принять во внимание, следует придать вес, придать высокий вес важным критериям и малый вес критериям, когда многие песни имеют одно и то же свойство, чтобы они не доминировали :
Чем ниже значение, получаемое этой процедурой, тем лучше перестановка списка.
Делать перестановку
Теперь вы можете взять эту формулу в math.stackexchange и попросить их рассказать вам, насколько безумно сложно и, возможно, практически невозможно найти оптимальное решение для чего угодно, кроме простого числа песен, или вы можете просто бросить такты и получить хорошее решение
Есть много способов сделать это, вот один:
Это несколько расточительный алгоритм, но его легко реализовать, и он может учитывать столько критериев, сколько нужно.
Оптимизации
Можно применить множество различных настроек и оптимизаций, вот некоторые из них:
При расчете значения качества не пытайтесь сравнивать песню с любой другой песней в списке, вместо этого просто проверяйте ее по 100 или около того ближайшим песням. Для обычных значений эта оптимизация скорости практически не влияет на качество результата.
Для редкого значения данного свойства может быть более эффективно отслеживать существующие экземпляры этого значения, чем искать их.
Если вы чувствуете, что важно, чтобы значения, имеющие несколько экземпляров, были расположены близко к четному, а не просто далеко друг от друга, вероятно, необходимо увеличить вес для этих конкретных значений, но не для других значений этого критерия.
Псевдослучайная функция, которая выбирает все возможные пары из списка в равном распределении, может иметь немного лучшую эффективность на выборку, чем обычная случайная выборка.
источник
Интересно, какие разные подходы люди используют. Я бы сделал следующее:
Основываясь на всех треках, сыгранных до сих пор, дайте каждому счет. Воспроизведите трек с наименьшим количеством баллов (или, в случае идентичных баллов, случайным, совпадающим с наименьшим баллом). Повторение.
Трудно, конечно, дать оценку. Для каждого возможного трека, который вы можете воспроизвести следующим, вам нужно будет просмотреть каждый (или ограниченное количество) треков, которые вы уже проиграли. Если [возможный следующий] трек и [недавно воспроизведенный] трек имеют что-то общее, вы добавляете к партитуре, в зависимости от того, сколько у них общего, что у них общего и как давно был [недавно воспроизведенный] трек играл. Вы, вероятно, хотели бы, чтобы «вообще ничего» было 0, поэтому вы можете начать со всех треков как 0.
Вы, вероятно, захотите поэкспериментировать с некоторыми созданными вручную плейлистами, чтобы понять математику правильно - хотите ли вы, чтобы общее количество слов совпадало, или квадрат числа общих слов, или квадратный корень из числа слов общего? Пройдите по всему списку воспроизведения, посмотрите, какие из них попали на вершину, как «наиболее распространенные», и отрегулируйте вручную факторы, чтобы получить правильный баланс. Возможно, вы хотите использовать буквенное обозначение, поэтому у «Дьюка Эллингтона» высокий балл по сравнению с «Дьюком Элингтоном», но еще более высокий балл по сравнению с «Кинг Элле Дутон» (если я не потерял ни одной буквы :) , Вы должны очень тщательно продумать, какие поля вы хотите сравнить, и хотите ли вы сравнить между полями. Вы могли бы даже рассмотреть биграммы (пары букв; в случае с Дюком Эллингтоном, "Du", "
Обратите внимание, что если у вас много конкретного исполнителя, этот исполнитель может быть упущен по приоритету - вы можете услышать трек уникального исполнителя 5 раз, прежде чем услышите все 10 своих треков Duke Ellington. Это может или не может быть то, что вы хотите. Вы можете избежать этого, настроив словарь всего, что вам нужно сравнивать, и как часто они встречаются, поэтому, если у вас много треков Duke Ellington, два трека, которые Duke Ellington, «менее похожи», чем два Билли Джо Шейвера. ,
Возможно, стоит даже заранее рассчитать таблицу с каждой комбинацией двух пар песен. Кроме того, когда вы решаете, какую песню играть дальше, вам нужно запомнить только лучшую песню на данный момент; если следующий, который нужно рассмотреть, имеет худший результат, чем лучшая песня на данный момент, вы можете перейти к следующему.
источник