Should/can 我在这个函数中使用了 `assoc` 来重新定义一个函数参数？

Question

我正在 Clojure 中为一个 class 项目实现 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 函数，我认为它是相似的。我想知道 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)))
          )))

所以现在我无法按照算法更改 p 和 x。我认为我可以使用 assoc 来做到这一点，但我认为它只适用于地图。可以用吗，有没有人推荐一下其他功能？

Answer 1

我认为根据您的评论，您最好使用 loop 和 recur。它与你现在拥有的确实没有太大区别，但它会消除递归函数调用。

Answer 2

assoc 不改变其参数。与 Clojure 中的所有其他基本集合操作一样，它 returns 一个新的不可变集合。

为了进行更新 "in place"，您将需要停止使用基本的 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)))))

Should/can 我在这个函数中使用了 `assoc` 来重新定义一个函数参数？

Should/can I use `assoc` in this function to redefine a function argument?

algorithm

clojure