将集合与集合集合进行比较的最佳算法

Question

在作为特定集的子集的有限集合集中查找集合的最佳算法是什么？

例如,如果

A = {1, 2}
B = {2, 3, 4}
C = {3, 5}
D = {6}

和X = {1, 2, 3, 5}

然后,A和C是X的子集.

是否有一种算法可以在线性时间复杂度中做到这一点？

实现注意:集合的成员通常来自非常有限的范围,因此,使用C++ bitset来实现算法可能是个好主意.不是吗？

编辑:集合中的集合数通常非常大于X中的元素数(在示例中).有没有办法在X中的元素数量方面做这个线性？可能使用哈希或其他东西？

Answer 1

让我们暂时假设64个可能的元素.

然后,如果表示各元素作为比特,则可以使用一个64位长的整数来表示每个组,然后:a & b是交集的a和b.
如果(且仅当)a是b当时的子集a & b == a.

当然,如果需要64位以上,可以使用bitset.

对于大范围的元素,使用哈希表来存储(一次)超集,然后迭代潜在的子集以检查是否所有元素都在其中.
它在输入大小(平均情况)中是线性的.

编辑:(对编辑问题的回应)

除非你预先存储了一些关于数据的信息 - 否则无法在betetr O(|X| + n*min{m,|X|})那里完成| X | 是集合X的大小,是集合n的数量,是集合m的平均大小.
这样做的原因是因为在最坏的情况下,你需要读取所有集合中的所有元素(因为你为每个集合读取的最后一个元素决定它是否是一个子集),因此如果没有先前的知识,我们就无法做到更好集.

建议的解决方案是:
Bitset:O(|X|*n)
Hash解决方案:( O(|X| + min{m,|X|}*n)平均情况)

虽然散列解决方案提供了更好的渐近复杂度,但是对于bitset来说常量要好得多,因此bitset解决方案可能会更快 |X|