包含超集

我正在寻找一个能够有效检查它是否包含我的集合超集的结构（“集合集合”）。包含超集

示例： A = {1，2} B = {2,3} C = {1,3} d = {1，2，3}

集合的集合S1 = { A，B}和另一个S2 = {d}

S1 contains A => true 
S1 contains C => false 
S2 contains A => true

对此的解决方案应该具有尽可能低的复杂性（不仅渐近）越好。

2014-10-28 JiriS

你的套件有多大？你有多少？ – 2014-10-28 12:12:18

集合通常包含少于5-10个字符串（或长整数），集合集合最多应包含约100-1000集，但在大多数情况下为10-100集。 – JiriS 2014-10-28 13:49:24

可以设置它们自己或集合的集合是否更改（即，是否可以插入/删除）还是全部是静态的？ – kraskevich 2014-10-28 16:02:46

-1

使用字典在位图中可能的不同元素和位置之间进行转换。然后将每个集合存储为位图。

考虑一组集的联合是一起讨论位图的问题。

检查一个集合是否是一组集合的一个子集正在检查位图结果和较小集合的位图。

这些操作应该很快。如果你真的是真的雄心勃勃，你可以从http://en.wikipedia.org/wiki/General-purpose_computing_on_graphics_processing_units开始，并找出如何将计算移动到GPU。

如果你有更大的集合，并且有时会得到错误的答案，那么你应该查找Bloom Filters。这可以让你用大大缩短的位图获得大部分正确的答案。

2014-10-28 23:10:48 btilly

回答