如何创建没有两首连续歌曲在同一调中的曲目列表
How to create a setlist where no two consecutive songs are in the same key
这是一个真正的问题，我正在尝试自动解决这个问题，所以我很乐意回答任何问题或要求澄清。
在此先感谢您的阅读，以及您对此的任何想法。 :)
编辑：为了与可能的重复问题区分开来，我希望 Clojure 特定的程序能够保证 return 正确答案并利用 Clojure 的核心和组合库......人们得到了答案！谢谢。
查找key-valid setlists的问题
我有一组 n 首歌曲（顺序无关紧要）。
每首歌只有一个调号，简称"key"，必须是"A" "A#" "B" "C" "C#" "D" "D#" "E" "F" "F#" "G" "G#".
12弦之一
多首歌曲可以"be in the same key"（分配给它们相同的整数）。
我需要 return 一个长度为 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"}
]
显然，并非总能找到一个关键有效的设置列表：
; input 2, with no solution:
[
{:title "Love Song" key "A"}
{:title "Inspirational Song" key "A"}
]
我试过的
我尝试编写一些东西，将在输入上使用 Clojure 的 group-by 以按密钥签名字符串进行分组（调用生成的映射 m），然后使用递归函数累加器（我将在其中建立最终的歌单）试图将 m 中的歌曲放入累加器中的有效位置。
但是我无法说服自己这种方法总能找到解决方案（如果存在的话）。
想法
我上面的想法似乎有道理，但可能需要添加回溯。我不知道如何实现这一点。
其他想法包括像数独游戏一样处理它并使用基于约束的方法 - 如果有人知道如何做到这一点，我会对使用 core.logic 的更具声明性的方法感兴趣。
未来的考虑：
- 使用某种随机策略更快地找到解决方案。
- 返回所有可能的键有效设置列表（如果存在）。
- 将另一首 属性 添加到歌曲中，例如速度，必须遵循不同的规则（例如，速度必须在整个曲目列表中单调增加）
- 求近似解（即同一键连续歌曲数最少），可能只有在找不到完美解的情况下，或者有其他约束条件需要满足的情况下。
我正在尝试在 Clojure 中执行此操作（我认为 core.logic 库可能会有所帮助）但显然该算法可以用任何语言完成。
您可以利用 clojure.math.combinatorics:
轻松做到这一点
(ns demo.core
(:use tupelo.core)
(:require
[clojure.string :as str]
[schema.core :as s]
[clojure.math.combinatorics :as combo]))
(def Song {:title s/Str :key s/Str})
(def SongPair [(s/one Song "s1")
(s/one Song "s2")])
(s/defn valid-pair?
[song-pair :- SongPair]
(let [[song-1 song-2] song-pair
key-1 (grab :key song-1)
key-2 (grab :key song-2)]
(not= key-1 key-2)))
(s/defn valid-set-list?
[set-list :- [Song]]
(let [song-pairs (partition 2 1 set-list)]
(every? valid-pair? song-pairs)))
(s/defn valid-sets
"Return a list of valid sets (song orderings) from songs that can follow the given lead-song."
[songs :- [Song]]
(let [all-set-lists (combo/permutations songs)
all-set-lists (mapv vec all-set-lists) ; convert set lists => vectors
valid-set-lists (set (filter valid-set-list? all-set-lists))]
valid-set-lists))
单元测试展示了它的实际效果：
(dotest
(let [songs [{:title "A1" :key "A"}
{:title "B1" :key "B"}]]
(is= (valid-sets songs)
#{[{:title "A1", :key "A"} {:title "B1", :key "B"}]
[{:title "B1", :key "B"} {:title "A1", :key "A"}]})))
(dotest
(let [songs [{:title "A1" :key "A"}
{:title "B1" :key "B"}
{:title "B2" :key "B"}]]
(is= (valid-sets songs)
#{[{:title "B2", :key "B"}
{:title "A1", :key "A"}
{:title "B1", :key "B"}]
[{:title "B1", :key "B"}
{:title "A1", :key "A"}
{:title "B2", :key "B"}]})))
(dotest
(let [songs [{:title "A1" :key "A"}
{:title "B1" :key "B"}
{:title "C1" :key "C"}]]
(is= (valid-sets songs)
#{[{:title "A1", :key "A"}
{:title "B1", :key "B"}
{:title "C1", :key "C"}]
[{:title "B1", :key "B"}
{:title "A1", :key "A"}
{:title "C1", :key "C"}]
[{:title "C1", :key "C"}
{:title "B1", :key "B"}
{:title "A1", :key "A"}]
[{:title "C1", :key "C"}
{:title "A1", :key "A"}
{:title "B1", :key "B"}]
[{:title "A1", :key "A"}
{:title "C1", :key "C"}
{:title "B1", :key "B"}]
[{:title "B1", :key "B"}
{:title "C1", :key "C"}
{:title "A1", :key "A"}]})))
对于您的示例，有 144 组可能的歌曲：
(dotest
(let [songs [{: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"}]]
(is= 144 (count (valid-sets songs)) )))
这是一种使用 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 的 通用 版本，它只查看值，而不是映射中的 :keys：
(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?))
这是一个真正的问题，我正在尝试自动解决这个问题，所以我很乐意回答任何问题或要求澄清。 在此先感谢您的阅读，以及您对此的任何想法。 :)
编辑：为了与可能的重复问题区分开来，我希望 Clojure 特定的程序能够保证 return 正确答案并利用 Clojure 的核心和组合库......人们得到了答案！谢谢。
查找key-valid setlists的问题
我有一组 n 首歌曲（顺序无关紧要）。
每首歌只有一个调号，简称"key"，必须是"A" "A#" "B" "C" "C#" "D" "D#" "E" "F" "F#" "G" "G#".
多首歌曲可以"be in the same key"（分配给它们相同的整数）。
我需要 return 一个长度为 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"}
]
显然，并非总能找到一个关键有效的设置列表：
; input 2, with no solution:
[
{:title "Love Song" key "A"}
{:title "Inspirational Song" key "A"}
]
我试过的
我尝试编写一些东西，将在输入上使用 Clojure 的 group-by 以按密钥签名字符串进行分组（调用生成的映射 m），然后使用递归函数累加器（我将在其中建立最终的歌单）试图将 m 中的歌曲放入累加器中的有效位置。
但是我无法说服自己这种方法总能找到解决方案（如果存在的话）。
想法
我上面的想法似乎有道理，但可能需要添加回溯。我不知道如何实现这一点。
其他想法包括像数独游戏一样处理它并使用基于约束的方法 - 如果有人知道如何做到这一点，我会对使用 core.logic 的更具声明性的方法感兴趣。
未来的考虑：
- 使用某种随机策略更快地找到解决方案。
- 返回所有可能的键有效设置列表（如果存在）。
- 将另一首 属性 添加到歌曲中，例如速度，必须遵循不同的规则（例如，速度必须在整个曲目列表中单调增加）
- 求近似解（即同一键连续歌曲数最少），可能只有在找不到完美解的情况下，或者有其他约束条件需要满足的情况下。
我正在尝试在 Clojure 中执行此操作（我认为 core.logic 库可能会有所帮助）但显然该算法可以用任何语言完成。
您可以利用 clojure.math.combinatorics:
(ns demo.core
(:use tupelo.core)
(:require
[clojure.string :as str]
[schema.core :as s]
[clojure.math.combinatorics :as combo]))
(def Song {:title s/Str :key s/Str})
(def SongPair [(s/one Song "s1")
(s/one Song "s2")])
(s/defn valid-pair?
[song-pair :- SongPair]
(let [[song-1 song-2] song-pair
key-1 (grab :key song-1)
key-2 (grab :key song-2)]
(not= key-1 key-2)))
(s/defn valid-set-list?
[set-list :- [Song]]
(let [song-pairs (partition 2 1 set-list)]
(every? valid-pair? song-pairs)))
(s/defn valid-sets
"Return a list of valid sets (song orderings) from songs that can follow the given lead-song."
[songs :- [Song]]
(let [all-set-lists (combo/permutations songs)
all-set-lists (mapv vec all-set-lists) ; convert set lists => vectors
valid-set-lists (set (filter valid-set-list? all-set-lists))]
valid-set-lists))
单元测试展示了它的实际效果：
(dotest
(let [songs [{:title "A1" :key "A"}
{:title "B1" :key "B"}]]
(is= (valid-sets songs)
#{[{:title "A1", :key "A"} {:title "B1", :key "B"}]
[{:title "B1", :key "B"} {:title "A1", :key "A"}]})))
(dotest
(let [songs [{:title "A1" :key "A"}
{:title "B1" :key "B"}
{:title "B2" :key "B"}]]
(is= (valid-sets songs)
#{[{:title "B2", :key "B"}
{:title "A1", :key "A"}
{:title "B1", :key "B"}]
[{:title "B1", :key "B"}
{:title "A1", :key "A"}
{:title "B2", :key "B"}]})))
(dotest
(let [songs [{:title "A1" :key "A"}
{:title "B1" :key "B"}
{:title "C1" :key "C"}]]
(is= (valid-sets songs)
#{[{:title "A1", :key "A"}
{:title "B1", :key "B"}
{:title "C1", :key "C"}]
[{:title "B1", :key "B"}
{:title "A1", :key "A"}
{:title "C1", :key "C"}]
[{:title "C1", :key "C"}
{:title "B1", :key "B"}
{:title "A1", :key "A"}]
[{:title "C1", :key "C"}
{:title "A1", :key "A"}
{:title "B1", :key "B"}]
[{:title "A1", :key "A"}
{:title "C1", :key "C"}
{:title "B1", :key "B"}]
[{:title "B1", :key "B"}
{:title "C1", :key "C"}
{:title "A1", :key "A"}]})))
对于您的示例，有 144 组可能的歌曲：
(dotest
(let [songs [{: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"}]]
(is= 144 (count (valid-sets songs)) )))
这是一种使用 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 的 通用 版本，它只查看值，而不是映射中的 :keys：
(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?))