algorithm - 包含超集

Question

我正在寻找一种结构(“集合的集合”)，它可以让我有效地检查它是否包含我的集合的超集。

例子: 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

此解决方案的复杂性应尽可能低(不仅是渐近的)。

Answer 1

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

获取一组集合的并集是将位图组合在一起的问题。

检查一个集合是否是一组集合的子集是检查位图的与运算结果是较小集合的位图。

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

如果您有更大的集合并且可以接受有时会得到错误的答案，那么您应该查看布隆过滤器。这使您可以使用明显更短的位图获得大部分正确答案。