clojure - 从向量中删除值的出现

Question

我一直在努力获得一个 Prüfer sequence在 Clojure 中实现的算法，主要是作为一种心理练习。虽然 what I have工作正常，我想知道是否有更简洁的方法从 map 和向量集合中删除某些内容，例如，如果我想删除以下所有 5 项:
{1 [2 3], 2 [1 4], 3 [1 5], 4 [2], 5 [3]}
留下:
{1 [2 3], 2 [1 4], 3 [1], 4 [2]}
我怀疑我拥有的结构是......次优......但这是我能想到的最简单的表示边缘集的方法。任何想法非常感谢!

Answer 1

TLDR:在这种情况下使用集合而不是向量。

首先，重复您选择的表示:无向图表示为从节点(由数字表示)到节点向量的映射。对于每条边 x-y，存在从 x 到包含 y 的向量的映射条目和从 y 到包含 x 的向量的条目。要移除节点 z 及其所有边，必须通过移除以 z 作为其键的映射条目以及通过从所有其他条目的向量中移除 z 来维护该不变量。

第一个操作——删除给定键的映射条目——很简单。没有条目的映射由表达式 (dissoc m 5) 给出，其中 m 是示例中的 map ， 5 是您希望从图中删除的节点。

第二个操作——从作为映射值的所有向量中删除一个元素——是一个复合操作，包括 1) 对映射的所有值执行某些操作 2) 从向量中删除一个元素。假设 2) 已解决(我们称之为 remove-from-vector )，我们可以通过多种方式来解决 1)(这里有三个示例):

(into {} (for [[k v] m]
           [k (remove-from-vector v z)]))

(into {} (map (fn [[k v]]
                [k (remove-from-vector v z)])
              m))

(zipmap (keys m)
        (map #(remove-from-vector % z) (vals m)))

问题 2) 提出了一些问题，因为没有内置的 Clojure 函数可以删除向量中间的元素。原因是它不是一个向量可以有效地做的事情。想象一下，您有一个包含 10000 个元素的向量，并且想要删除索引为 5000 的向量。要构造新向量，必须将 4999 个元素连接到包含索引 0 到 4999 的子向量的末尾。显然，我们将最好使用以更好的方式处理任意元素删除的数据结构。

为了解决这个问题，我们可以重新设计表示。实际上有一个数据结构可以更好地处理删除:集合。如果一个集合包含 10000 个具有均匀分布的哈希值的值，其内部树的高度为 3。这意味着删除集合中的一个元素需要 3 个内部步骤，而不是 10000 的数量级。如果我们使用集合示例 map 不是向量，而是如下所示:

{1 #{2 3}, 2 #{1 4}, 3 #{1 5}, 4 #{2}, 5 #{3}}

For 设置了我们的 remove-from-vector对应的操作以上是 disj – conj的反面.可以像这样实现具有新表示的最终解决方案:

(defn remove-node [graph node]
  (into {} (for [[k v] (dissoc graph node)]
             [k (disj v node)])))