7

我正在寻找一个抽象的数据结构，它表示集合的集合，这样集合中的任何集合都不是集合中另一个集合的子集。

这意味着在插入时将满足以下条件：

A. 插入一个已经是另一个元素子集的元素将返回原始集合。

B. 插入作为任何其他元素的超集的元素将导致添加超集并删除子集的集合。

假设对集合的元素进行排序，则可以使用前缀树来表示集合。这允许非常快速地处理条件 A（即检查条件所需的时间比插入子集的时间要长），但是满足条件 B 需要时间。

我想知道是否存在允许快速满足 B 的数据结构。

4

4 回答 4

3

简单的方法是保留一个集合列表，并对每个传入集合执行线性搜索（测试传入是否是子集）。

对于线性搜索，这显然在 O(n) 时间内运行，对于传入集的大小可能在 O(m) 时间内运行。因此 O(n*m) 总时间（集合数与每个集合的大小）。

当然，最明显的优化是对集合大小进行索引。然后，您只针对大小相同或更大的每个传入集合进行测试。（一个集合不能是任何较小集合的子集，呵呵！）。

想到的下一个优化是在元素索引中创建。因此，对于每个传入集合，您会找到包含每个元素的每个集合的交集。换句话说，如果对于传入的集合 {a,b,c}，我们发现元素 {a} 存在于集合 A、B 和 D 中，则元素 {b} 存在于 B、E 和 F 中，并且 {c}存在于 A、B 和 Z ... 那么传入集是 B 的子集（{A, B, D}、{B, E, F} 和 {A, B, Z} 的交集）。

所以，对我来说，这听起来像 O(m*log(n)) 复杂度。（我们必须对每个传入集合的每个元素执行散列搜索）。插入的顺序也应该相同（将新集合的 ID 插入到每个元素的映射中）。（当然，在 Big-O 分析中，2*O(m log(n)) 减少到 O(m log(n))）。

于 2009-11-21T01:45:15.010 回答
0

一个简单的想法，它将在 O(K) 中起作用，其中 K 是要添加的元素的大小。

  • 以任何你想要的方式保持集合
  • 保留 set_id 的地图 -> set_size
  • 保留对象的地图-> set_id

A 和 B 都是 O(K)。

于 2009-11-15T11:46:31.707 回答
0

如果您的集合 A、B、... 的各个成员被映射到不同（且相对）的素数，并且在每个集合旁边，您将所有成员的乘积存储为 p(A)、p(B) 等，那么子集和超集可以通过 p(X) 是否是 p(Y) 的因子来找到，反之亦然。

我猜你最终可能会得到一些非常大的数字，但它在理论上是有效的。

例如：

如果 [abcd] -> [2 3 5 7], p(abc) = 30, p(abd) = 42, p(bc) = 15, p(abcd) = 210

于 2009-11-21T05:13:35.263 回答
0

多么愚蠢的网站！我现在已经注册了，所以可能会在适当的时候对昨天的东西发表评论。然而，在那之前……

@Stephen C：虽然我相信我的英语足够，但我似乎已经获得了一个解释器：然而，他错过了一些内容，他的评论应该如下所示：

@Stephen C：找到任意数字的因子确实是NP完整的，但在这里不相关。问题是两个数字中的较小者是否准确地除以较大的简单模数运算。例如，p(bc)=15 是 p(abcd)=210 的除数，因此 bc 是 abcd 的子集（集合 abd 和 abc 也是如此）。

向现有的 N 个集合集合添加一个新集合 S 是 O(N)，假设无论 N 多少，大数的比较和除法都需要大致相同的时间。

对于集合集合中的每个现有条目 E，如果 p(S) < p(E) 并且 p(S) 正好除 p(E) 则停止。如果 p(S) = p(E)，停止。如果 p(S) > p(E) 并且 p(E) 正好整除 p(S)，则删除 E。如果您到达集合的末尾，请添加 S。一组 BigNums 可以工作。

@JL：如果您想成为我的现场跟踪者，请努力 1）准确地增加价值 2）。

于 2009-11-22T06:02:53.837 回答