Как создать сет-лист, в котором нет двух последовательных песен в одном ключе

Это реальная проблема, решение которой я пытаюсь автоматизировать, поэтому я с удовольствием отвечу на любые вопросы или просьбы о разъяснении. Заранее спасибо за чтение и за любые мысли, которые у вас могут возникнуть по этому поводу. :)

Edit: чтобы отличить от возможного дублирующего вопроса, я надеялся на программы Clojure, которые гарантированно возвращают правильный ответ и используют библиотеки ядра и комбинаторики Clojure... и у людей были ответы! Благодарю ты.

Задача поиска допустимых наборов ключей

У меня есть набор 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"}
]

Очевидно, что не всегда возможно найти ключ-допустимый setlist:

; input 2, with no solution:
[
    {:title "Love Song" key "A"}
    {:title "Inspirational Song" key "A"}
]

Что я пробовал

Я попытался написать что-то, что будет использовать Clojure group-by на входе, чтобы сгруппировать по ключу строка подписи (вызов результирующей карты m), а затем рекурсивная функция с аккумулятором (где я построю окончательный setlist), которая пытается поместить песню из m в аккумулятор в допустимой позиции.

Однако я не мог убедить себя, что этот метод всегда найдет решение, если оно существует.

Идеи

Моя идея выше казалась правдоподобной, но, возможно, потребуется добавить отступление. Я не знаю, с верхней части моей головы, как осуществить это. Другие идеи включают в себя рассмотрение этого как судоку и использование метода на основе ограничений - я был бы заинтересован в более декларативном подходе, использующем core.logic, Если кто-то знает, как это сделать.

Будущие соображения:

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

Я пытаюсь сделать это в Clojure (я думал, что библиотека core.logic может помочь), но очевидно, что алгоритм может быть выполнен на любом языке.