2

假设我有 4 个不同的值 A、B、C、D，并附加了一组标识符。

A={1,2,3,4,5}
B={8,9,4}
C={3,4,5}
D={12,8}

并且给定一组标识符 {1,30,3,4,5,12,8} 我希望它返回 C 和 D。即从一组 S 是超集的集合中检索所有集合。

是否有任何算法可以有效地执行此任务（最好具有低内存复杂性。使用外部设备存储数据不是一种选择）？一个简单的解决方案是为超集 S 中的每个成员检索包含该成员的集合列表（基本上是倒排索引），并为每个返回的集合检查他的所有成员是否都在超集中。不幸的是，由于平均而言，超集将包含每个集合的至少一个成员，因此这种方法会产生显着且不可接受的性能损失。

我正在尝试在 Java 中执行此操作。集合由整数组成，它们标识的值是一个对象。集合的集合不是静态的，并且在执行过程中必然会发生变化。不过，设定的数量会有一些限制。套装大小不受限制。但平均而言，它在 1 到 20 之间。

4

3 回答 3

3
  1. 遍历S中的每个元素x。
  2. 对于x ∈ t的每个集合t ，增加一个与t相关联的计数器（称为t count）。
  3. 毕竟，对于每个集合t其中t count = | t |，你知道t ⊆ S。

应用。

在第 2 步之后。

A计数= 4，
B计数= 1，
C计数= 3，
D计数= 2。

步骤 3 处理。

计数≠| A | (4 ≠ 5) — 拒绝，
B计数≠ |B| (1 ≠ 3) — 拒绝，
C计数= |C| (3 = 3) — 接受，
D计数= |D| (2 = 2) — 接受。

于 2009-12-26T10:03:11.103 回答
1

cgkanchi 注意后的注意事项：以下算法是在您不真正使用集合而是数组的假设下进行的。如果不是这种情况，您应该寻找一种实现集合交集的方法，然后问题就很简单了。这是关于如何使用数组实现交集的概念。

  1. 使用 heapsort 对所有集合进行就地排序 O(1) 空间。它以 O(nlogn) 运行，很快它就会给你回报。

  2. 对于L所有集合中的每一个集合：

    2.1。j = 0

    2.2. 对于 中的i元素L：

    2.2.1。从j元素开始查找其他拒绝L[i]的元素。如果并且足够大，请使用二分搜索或插值搜索（对于第二个，请查看您的数据分布）SL[i] = S[j]LS

    2.3. 接受

于 2009-12-29T00:36:47.183 回答
0

至于 Java，我会使用Hashtable作为S中元素的查找表。然后对于X中的每个元素，您要测试的集合是否是S的子集，测试它是否在查找表中。如果X的所有元素也在S中，则S是X的超集。

于 2009-12-26T10:18:33.627 回答