我正在Clojure中为一个类项目实现Bron-Kerbosch算法,但遇到了一些问题问题在于算法的最后几行

BronKerbosch1(R, P, X):
 if P and X are both empty:
       report R as a maximal clique
   for each vertex v in P:
       BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
       P := P \ {v} ;This line
       X := X ⋃ {v} ;This line

我知道在clojure中没有“set x=something”的意思。但我知道有一个功能,我认为是相似的我想知道assoc是否适合完成我的实现。
在我的实现图中是这样表示的
[#{1 3 2} #{0 3 2} #{0 1 3} #{0 1 2}]

其中第0个节点表示为向量中的第一个集合,集合中的值表示其他节点的边。所以上面的表示一个有4个节点的图是完整的(所有节点都连接到所有其他节点)。
到目前为止,我的算法实现是
(defn neighV [graph, v]
  (let [ret-list (for [i (range (count graph)) :when (contains? (graph i) v)] i)]
    ret-list))

(defn Bron-Kerbosch [r, p, x, graph, cliques]
  (cond (and (empty? p) (empty? x)) (conj cliques r)
        :else
        (for [i (range (count p))]
          (conj cliques (Bron-Kerbosch (conj r i) (disj p (neighV graph i) (disj x (neighV graph i)) graph cliques)))
          )))

所以现在我不得不按照算法修改assocp我想我可以用x来做这件事,但我认为它只适用于地图。是否可以使用,是否有人可以推荐其他功能?

最佳答案

assoc不会改变其参数。与clojure中的所有其他基本集合操作一样,它返回一个新的不可变集合。
为了进行“就地”更新,您需要停止使用基本的Clojure数据类型,并使用本地Java类型,如java.util.HashSet
另一个(也是首选)选项是重构算法,以便将所有更新传递到代码的下一次迭代或递归。
下面是根据这种风格调整代码的初步尝试,但要注意的是,可能需要从递归调用中提取内部修改:

(defn Bron-Kerbosch
  [r p x graph cliques]
  (if (every? empty? [p x])
    (conj cliques r)
    (reduce (fn [[cliques p x] v]
              (let [neigh (neighV graph v)]
                [(conj cliques
                       ;; do we need to propagate updates to p and x
                       ;; from this call back up to this scope?
                       (Bron-Kerbosch (conj r v)
                                      (disj p neigh)
                                      (disj x neigh)
                                      graph
                                      cliques))
                 ;; here we pass on the new values for p and x
                 (disj p v)
                 (conj x v)]))
            [cliques p x]
            (range (count p)))))

07-28 12:03