algorithm - 如何创建没有两首连续歌曲在同一调中的轨道列表

Question

这是一个真正的问题，我正在尝试自动解决这个问题，所以我很乐意回答任何问题或澄清要求。 在此先感谢您的阅读，以及您对此的任何想法。 :)

编辑:为了与可能的重复问题区分开来，我希望 Clojure 特定的程序能够保证返回正确的答案并利用 Clojure 的核心和组合库……人们已经得到了答案!谢谢。

寻找关键有效集合列表的问题

我有一组 n 首歌曲(顺序无关紧要)。

每首歌都有一个调号，简称“key”，必须是12个字符串之一 "A""A#""B""C""C#""D""D#"“E”“F”“F#”“G”“G#”。

多首歌曲可以“在同一个键中”(分配给它们的相同整数)。

我需要返回一个长度为 n 的有序列表，其中包含每首歌曲，其顺序不会让两首连续的歌曲出现在同一调中，如果这样列表可以查到。 (我将其称为 key-valid 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"}
]

显然，并非总能找到 key 有效的设置列表:

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

我尝试过的

我尝试编写一些东西，将在输入上使用 Clojure 的 group-by 以按 key 签名字符串进行分组(调用生成的映射 m)，然后有一个带有累加器的递归函数(我将在其中建立最终的轨道列表)尝试将 m 中的歌曲放入有效位置的累加器中。

但是我无法说服自己这种方法总能找到解决方案(如果存在的话)。

想法

我上面的想法似乎有道理，但可能需要添加回溯。我不知道如何实现这一点。

其他想法包括像数独游戏一样处理它并使用基于约束的方法 - 如果有人知道如何做到这一点，我会对使用 core.logic 的更具声明性的方法感兴趣。

future 的考虑:

1. 使用某种随机策略更快地找到解决方案。
2. 返回所有可能的键有效集合列表(如果存在)。
3. 为歌曲添加另一个属性，例如速度，必须遵循不同的规则(例如，速度必须在整个轨道列表中单调增加)
4. 获得近似解决方案(即同一调中连续歌曲的最少数量)，可能仅在无法找到完美解决方案时，或者可能在需要满足其他约束条件时。

我正尝试在 Clojure 中执行此操作(我认为 core.logic 库可能会有所帮助)但显然该算法可以用任何语言完成。

Answer 1

这是一种使用 core.logic 来实现的方法。

我们将定义 secondo(如 firsto)以在下一个函数中查看集合中每对项目的第二个项目。

(defn secondo [l s]
  (fresh [x]
    (resto l x)
    (firsto x s)))   

我们将定义 nonconseco 以递归检查是否没有连续值:

(defn nonconseco [l]
  (conde
    [(== l ())]
    [(fresh [x] (== l (list x)))]
    [(fresh [lhead lsecond ltail]
       (conso lhead ltail l)
       (secondo l lsecond)
       (project [lhead lsecond] ;; project to get your map keys
         (!= (:key lhead) (:key lsecond)))
       (nonconseco ltail))]))

还有一个函数，用于查找没有任何连续相同值的 coll 的第一个排列:

(defn non-consecutive [coll]
  (first
    (run 1 [q]
      (permuteo coll q)
      (nonconseco q))))

这可以用于您的示例输入:

(non-consecutive
  [{: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 "Power Ballad" :key "D"}])
=>
({:title "Love Song", :key "A"}
 {:title "Breakup Song", :key "B"}
 {:title "Inspirational Song", :key "A"}
 {:title "Deep House Track", :key "F#"}
 {:title "Summer Song", :key "A"}
 {:title "Power Ballad", :key "D"})

这里是 nonconseco 的通用版本，它只查看值，而不是 map 中的 :key:

(defn nonconseco [l]
  (conde
    [(== l ())]
    [(fresh [x] (== l (list x)))]
    [(fresh [lhead lsecond ltail]
       (conso lhead ltail l)
       (secondo l lsecond)
       (!= lhead lsecond)
       (nonconseco ltail))]))

 (non-consecutive [1 1 2 2 3 3 4 4 5 5 5])
 => (3 2 3 4 2 4 5 1 5 1 5)

更新:这是一个使用谓词函数而不是关系逻辑的更快版本:

(defn non-consecutive? [coll]
  (every? (partial apply not=) (partition 2 1 coll)))

然后使用 core.logic 的 pred 将该谓词应用于逻辑变量:

(run 10 [q]
  (permuteo coll q)
  (pred q non-consecutive?))