在 Clojure Bron-Kerbosch 实现中正确使用集合

Question

我目前正在尝试在 Bron-Kerbosch 算法的 Clojure 实现中正确有效地使用集合和 clojure.set 命名空间，但遇到了困难。

我正在尝试重构我当前的实现

(defn BK [r p x graph]
  (if (and (empty? p) (empty? x))
    [(set r)]
    (loop [p p, x x, cliques []]
      (if (empty? p)
        cliques
        (let [v (first p)
              nv (graph v)
              cliques (into cliques
                            (BK (into r (list v))
                                (filter nv p)
                                (filter nv x)
                                graph))
              p (rest p)
              x (into x (list v))]
          (recur p x cliques))))))

进入使用 clojure.set 名称空间的东西

(defn BK3 [r p x graph]
  (if (and (empty? p) (empty? x))
    [(set r)]
    (loop [p p, x x, cliques []]
      (if (empty? p)
        cliques
        (let [v (first p)
              nv (graph v)
              cliques (into cliques
                            (BK3 (clojure.set/union (set (list v)) r)
                                 (clojure.set/difference p nv)
                                 (clojure.set/difference x nv)
                                 graph))
              p (rest p)
              x (clojure.set/union (set (list v)) x)]
          (recur p x cliques))))))

(defn get-BK3 [graph]
  (BK3 (set '()) (set (doall (range (count graph)))) (set '()) graph))

虽然当前的实现会导致 Whosebug。这是一个简短的 SSCCE，其中包含运行评估函数 http://pastebin.com/PVxJidGB.

的所有必要代码

如果我在函数中的 (if (empty? p)) 之前放置一个 prn 形式，我可以看到集合 p 被改变一次，再也不会改变，而且集合 x 永远不会添加到。打印并重复以下内容，直到发生堆栈溢出。

finalproject.core> (get-BK3 (random-graph 10 20))
"P: " #{0 7 1 4 6 3 2 9 5 8} " X: " #{}
-----------------
"P: " #{0 7 4 6 3 2 9 8} " X: " #{}
-----------------
"P: " #{0 7 4 6 3 2 9 8} " X: " #{}
-----------------
"P: " #{0 7 4 6 3 2 9 8} " X: " #{}
-----------------
....

这一定意味着在每次递归调用 BK3 时，集合 p 没有从中删除集合 nv 吗？虽然审查 clojure.set/difference help page 它应该这样做吗？是我读错了页面还是有一些拼写错误导致堆栈溢出？

这是我不明白的第一个问题。我的下一个问题是 first 和 rest 不 return 集合（#{0 1 2}）而是列表（(0 1 2)）。如果将列表传递给任何 clojure.set 函数，则会抛出错误。 return 设置的 first 和 rest 是否有任何替代方案？

编辑：这是来自维基百科的伪代码实现，带有正确的集合概念符号。我想我对符号的解释可能不正确？

Answer 1

既然你有 Whosebug，那么从概念上讲，这可能会发生在你的代码中：

(clojure.set/difference #{1,2,3,4,5} #{4})
#{1 3 2 5}
user> (clojure.set/difference #{1,2,3,5} #{4})
#{1 3 2 5}

其中 p 是 #{1 2 3 4 5}，nv 是 #{4}。

在递归中，p 变为 #{1 3 2 5} 然后你再次得到相同的 v（因为你没有自循环，因此 4 不是 v 更早..）因此相同 nv #{4}

即两组中的第一组相同..

user> (first #{1 2 3 4 5})
1
user> (first #{ 1 2 3 5})
1

同样的递归..和Whosebug..

Answer 2

来自维基百科的该算法的伪代码版本中的递归调用使用集合交集，而不是集合差异。您可以使用 clojure.set/intersection 来计算两个持久集的交集。
设置差异用在for each循环体的第二行。在您的代码中，对应的表达式是 (rest p)，但这会生成 p 除 (first p) 之外的所有元素的序列，而不是集合。你会想要使用 (disj p (first p)) 代替（或者我想 (disj p v)，使用之前介绍的本地）。
set/union 和 into 对于将单个元素添加到集合中都太过分了——请改用 conj。

Answer 3

正如@michat 所回答的，在维基百科公式中递归调用是设置 intersection 而不是设置 difference，这不是相同。在数学中，clojure.set/difference的匹配函数是set complement.

关于 first 和 rest 与 set 的问题，您可以使用 first，这将产生一个元素，该元素在下一个顺序中不是必需的（但在算法中并不重要) 和 disj 从集合中删除所选元素。

请注意，您可以将 (set '()) 简化为 #{}。

以下是 clojure.set 的工作版本，test/bench 显示 set 版本的一些性能改进：

(require '[clojure.set :as s])

(defn BK4 [r p x graph]
  (if (and (empty? p) (empty? x))
    [r] ;; r is already a set
    (loop [p p, x x, cliques []]
      (if (empty? p)
        cliques
        (let [v (first p) ;; p is a set, first is not necessary the next in sequence
              nv (graph v) ;; take v-th set from graph
              cliques (concat cliques
                            (BK4 (conj r v) ;; add v to the set r
                                 (s/intersection p nv)
                                 (s/intersection x nv)
                                 graph))]
          (recur (disj p v) (conj x v) cliques))))))

(defn get-BK4 [graph]
  (BK4 #{} (set (range (count graph))) #{} graph))

测试：

(let [graph (doall (random-graph 1000 1000))
      bk (time (get-BK graph))
      bk4 (time (get-BK4 graph))]
  (if (= bk bk4)
    (println "Seems ok")
    (println "ko")))

打印（在 MBP 2.5 GHz Intel Core i7 上）

"Elapsed time: 243.533768 msecs"
"Elapsed time: 19.228952 msecs"
Seems ok

在 Clojure Bron-Kerbosch 实现中正确使用集合

Proper use of sets in Clojure Bron-Kerbosch implementation

clojure