Это реальная проблема, которую я пытаюсь автоматизировать, поэтому я с удовольствием отвечу на любые вопросы или просьбы о разъяснениях.
Заранее благодарим за чтение и за любые мысли, которые могут у вас возникнуть по этому поводу. :)
Редактировать: Чтобы отличить от возможного дублирующего вопроса, я надеялся на программы, специфичные для Clojure, которые гарантированно вернут правильный ответ и используют библиотеки ядра и комбинаторики Clojure ... и у людей были ответы! Спасибо.
Проблема поиска допустимых ключей setlists
У меня есть набор n песен (порядок не имеет значения).
Каждая песня имеет ровно одну ключевую подпись, или сокращенно «ключ», который должен быть одной из 12 строк "A" "A#" "B" "C" "C#" "D" "D#" "E" "F" "F#" "G" "G#".
Несколько песен могут быть «в одном ключе» (им назначено одинаковое целое число).
Мне нужно вернуть упорядоченный список длиной n, содержащий каждую песню, в таком порядке, чтобы никакие две последовательные песни не находились в одной и той же клавише , если такой список можно найти. (Я назову это допустимым ключом setlist ). Это потому, что звучит немного скучно, когда вы слышите две песни подряд в одной и той же клавише. Звучит так, будто это две части одной массивной песни.
; input 1, here given as a list but really an unordered set, not a key-valid setlist because there are a bunch of songs in the key of A consecutively:
[
{:title "Deep House Track" :key "F#"}
{:title "Breakup Song" :key "B"}
{:title "Love Song" :key "A"}
{:title "Inspirational Song" :key "A"}
{:title "Summer Song" :key "A"}
{:title "Summer Song" :key "A"}
{:title "Power Ballad" :key "D"}
]
; output 1 will be:
[
{:title "Love Song" :key "A"}
{:title "Breakup Song" :key "B"}
{:title "Inspirational Song" :key "A"}
{:title "Power Ballad" :key "D"}
{:title "Summer Song" :key "A"}
{:title "Deep House Track" :key "F#"}
{:title "Summer Song" :key "A"}
]
Очевидно, что не всегда можно найти правильный список ключей:
; input 2, with no solution:
[
{:title "Love Song" key "A"}
{:title "Inspirational Song" key "A"}
]
Что я пробовал
Я пытался написать что-то, что будет использовать group-by Clojure на входе, чтобы сгруппировать по строке ключевой подписи (вызвать полученную карту m), а затем иметь рекурсивную функцию с аккумулятором (где я буду строить окончательный сет-лист), который пытается поместить песню из m в аккумулятор в допустимую позицию.
Однако я не мог убедить себя, что этот метод всегда найдет решение, если оно существует.
Идеи
Моя идея, представленная выше, казалась правдоподобной, но, возможно, потребуется добавить возврат. Я не знаю, изо всех сил, как это реализовать.
Другие идеи включают обработку этого типа судоку и использование метода, основанного на ограничениях - я был бы заинтересован в более декларативном подходе с использованием core.logic, если кто-нибудь знает, как это сделать.
Будущие соображения:
- Использование какой-то рандомизированной стратегии для быстрого поиска решения.
- Возвращение всех возможных наборов ключей, допустимых для ключа, если таковые существуют.
- Добавление к песне другого свойства, например темп, который должен следовать другому правилу (например, темп должен монотонно увеличиваться во всем сет-листе)
- Получение приблизительных решений (т. Е. С минимальным количеством последовательных песен в одном и том же ключе), возможно, только когда не может быть найдено идеальное решение, или может быть, когда есть другие ограничения, которые должны быть удовлетворены.
Я пытаюсь сделать это в Clojure (я думал, что библиотека core.logic может помочь), но, очевидно, алгоритм может быть выполнен на любом языке.