clojure 中列表的`conj` 和`disj`？可能用于此的其他数据结构？包含中电

Question

对于一个 class 项目，我正在实施 Bron-Kerbosch algorithm 以在图中查找最大派系。在 SO 上其他人的帮助下，我已经解决了最后几个问题。

此 link (http://pastebin.com/2GUPZFnR) 包含概述问题的当前实施的 SSCCE。我认为问题在于我使用 disj 来查找两个列表的交集。我认为这是基于我使用 "sanity" 输入调用 BK-Call 时给出的错误。

fptests.core> (BK-Call (sanity1))
ClassCastException clojure.lang.PersistentList$EmptyList cannot be cast to clojure.lang.IPersistentSet  clojure.core/disj (core.clj:1449)

此错误可追溯到我的 Bron-Kerbosch 函数本身的几行代码

(defn Bron-Kerbosch [r p x graph cliques]
  (cond (and (empty? p) (empty? x)) (conj cliques r)
        :else
        (let [neigh (neighV graph (dec (count p)))]
          (loop [loop-clq '(cliques)
                 loop-cnt '(dec (count p))
                 loop-p '(p)
                 loop-x '(x)]
            (cond (= -1 loop-cnt) loop-clq
                  :else
                  (recur (conj loop-clq (Bron-Kerbosch (conj r loop-cnt) (conj p neigh) (disj x neigh)))
                         (dec loop-cnt)
                         (disj p loop-cnt)
                         (conj x loop-cnt)))))))

具体在recur形式的函数的递归调用中。尽管这个问题我认为适用于 conj 和 disj 的所有使用。似乎 conj "works" 但不是我假设的方式。

fptests.core> (disj '(1) '(1 2 3))
ClassCastException clojure.lang.PersistentList cannot be cast to clojure.lang.IPersistentSet  clojure.core/disj (core.clj:1449)
fptests.core> (conj '(1) '(2 3))
((2 3) 1)

我假设 (conj '(1) '(2 3)) 会 return (1 2 3) 而不是 (1 (2 3))。所以看来我在整个函数中使用列表是问题所在。有什么办法可以解决这个问题吗？

我不得不想象有像 conj 和 disj 这样的函数可以处理列表。如果这不是真的，我想我的另一个选择是在算法中使用其他一些数据结构。什么是合适的？

Answer 1

使用 cons、rest 和 concat。

user=> (cons 1 '(2 3))
(1 2 3)
user=> (cons '(1) '(2 3))
((1) 2 3)
user=> (cons 1 ())
(1)
user=> (rest '(1 2 3))
(2 3)
user=> (concat '(1) '(2 3))
(1 2 3)

Answer 2

我确实建议使用更适合手头问题的数据结构，即集合。

您已经在图形表示中使用了 Clojure 哈希集（(repeat n #{}) in empty-graph）； Bron-Kerbosch 阶跃函数的 r、p 和 x 参数在概念上都是集合，因此也可以将它们表示为 Clojure 集合。

通过选择表示，事情会变得更简单 - 集合交集可以使用 clojure.set/intersection、disj 用于删除单个键等来计算。

另外，在 Bron-Kerbosch 中使用 if 而不是 cond 会更自然（该函数中的两个 cond 实际上只有两个分支机构）。更重要的是，您需要从 loop – '(dec (count p))（注意 '）中的 init 表达式中删除引号，举个例子，是一个二元素列表，不是一个数字。（函数名包含大写字母在 Clojure 中也有些不寻常，但这当然纯粹是风格问题。）

clojure 中列表的`conj` 和`disj`？可能用于此的其他数据结构？包含中电

`conj` and `disj` for lists in clojure? Possible other data structures to use for this? Contains SCCEE

clojure

data-structures