代码之家 › 专栏 › 技术社区 › R u c k s a c k

如何创建一个集合列表,其中没有两首连续的歌曲在同一个键中

constraint-programming combinatorics clojure algorithm

R u c k s a c k · 技术社区 · 6 年前

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

编辑:为了区别可能重复的问题,我希望Clojure特定的程序能够保证返回正确的答案,并利用Clojure的核心库和组合库。。。人们都有答案!非常感谢。

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

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

每首歌都有一个密钥签名,简称“key”,必须是12个字符串中的一个 "A" "A#" "B" "C" "C#" "D" "D#" "E" "F" "F#" "G" "G#" 。

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

我需要返回一个有序的长度列表 N 包含了每首歌, 顺序应确保没有两首连续的歌曲在同一个键中 ,如果可以找到这样的列表。(我称之为 密钥有效集合列表 )这是因为当你在同一个调子里连续听到两首歌时,听起来有点无聊。听起来有点像是一首大型歌曲的两个部分。

; 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做到这一点(我认为 果心思维方式 库可能会有所帮助),但显然该算法可以用任何语言完成。

2 回复 | 直到 6 年前

Taylor Wood 6 年前

这里有一种使用core的方法。思维方式

我们将定义 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"})

这里有一个 通用的 版本 Noncoseco公司 它只关注值,而不是 :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。逻辑的 pred 要将该谓词应用于逻辑变量,请执行以下操作:

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

Alan Thompson 6 年前

通过利用 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)) )))