clojure - 在 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))

尽管当前的实现会导致 StackOverflow。这是一个简短的 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 不返回集合 (#{0 1 2}) 而是列表 ((0 1 2))。如果将列表传递给任何 clojure.set 函数，则会引发错误。除了返回集合的 first 和 rest 之外，还有其他选择吗？

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

Answer 1

正如@michat所回答的，在维基百科公式中，递归调用是使用setintersection而不是setdifference，它们是不一样的。在数学中，clojure.set/difference 的匹配函数是 set complement .

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

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

以下是 clojure.set 的工作版本，具有非常快速的测试/基准，显示了 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