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

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就是set intersection a 和 b。
如果(且仅当)a 是b 的子集，则a & b == a。

当然，如果您需要超过 64 位，您可以使用位集。

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

---

编辑:(对已编辑问题的回复)

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

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

虽然散列解决方案提供了更好的渐近复杂性，但常量对于位集来说要好得多 - 因此对于小的 |X|

，位集解决方案可能会更快