algorithm - 我应该/可以在此函数中使用 `assoc` 来重新定义函数参数吗？

Question

我正在为一个类(class)项目在 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 函数，我认为它是相似的。我想知道 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 来做到这一点，但我认为它只适用于 map 。是否可以使用，有人可以推荐其他功能吗？

Answer 1

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