不包含集合中另一个集合的子集的集合的集合

Question

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

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

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

B.插入作为任何其他元素的超集的元素将产生一个添加了超集并删除了子集的集合。

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

我想知道是否有数据结构可以让B也能很快得到满足。

Answer 1

在琐碎的做法是保持的集的列表，并通过对于每个传入组进行线性搜索（测试如果传入是其子集）。

这明显在O（n）的时间为用于进入集的大小线性搜索和可能O（M）尺寸上运行。因此O（n * m个）总时间（集合与每一组的大小数）。

最明显的优化，当然，是在集大小指数。然后，你只测试每个传入的集合针对那些等于或更大尺寸的。 （A组不能被任何较小的一组的一个子集，杜！）。

这想到的下一个优化是在元件的索引来创建。因此，对于每个进入的组你会发现包含各元素的每个集合的交集。换句话说，如果，传入集合{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到每个元素的映射的）上。 （在大O分析2 * O（米的log（n））降低至O（米的log（n）），当然）。

Answer 2

这是一个简单的想法，适用于 O(K)，其中 K 是要添加的元素的大小。

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

A 和 B 都是 O(K)。

Answer 3

如果您的集合A的个人会员，B，...映射到不同的（相对）的素数，和并排设置你存储所有成员的产品为P（A），P（B）等，然后子组和超集可以由p（X）是否为p（Y），或反之亦然的因子被发现。

您可以用一些非常大的数字我想结束了，但它在理论上的工作。

例如：

如果[A B C d] - > [2 3 5 7]，P（ABC）= 30，P（ABD）= 42，P（BC）= 15，P（ABCD）= 210

Answer 4

什么是傻乎乎的网站！现在我已经注册了，所以可能会在适当的时候能够从昨天起东西发表评论。在此之前，但是...

@Stephen C：但我相信我的英语水平是适当的我似乎已经获得了explicator：他已经错过了位，但是，他的评论应如下：

---

  

@Stephen C：发现的因素   任意数量的确是NP完全性，但在这里不相关。该   问题是两者是否较小   数准确分割越大，一个   简单模数操作。例如，   P（BC）= 15为p（ABCD）= 210的除数，   所以BC是ABCD的一个子集（如同套ABD   和ABC）。

     

添加新的集合S到N的现有收集组是O（N），假定不管所述大量的比较和除法需要大约N的同一时间。

     

有关的集集合中的每个现有条目E，停止，如果P（S）    P（E）和p（E）除以P（S）完全相同。加s，如果你到了集合的末尾。数组   的大数将工作。

---

@JL：如果你想成为我的现场死缠烂打，请努力1）增加值2）准确