algorithm - 在一组集合中查找子集和超集的有效方法

Question

是否有任何有效的算法或数据结构来查找集合集合的超集和子集？

例子:

# collection of sets
>>> col = [{1,2,3},{2,3,4},{4,5,6,7}]

>>> subsets_of({1,2,3,4}, col)
[{1,2,3},{2,3,4}]

>>> supersets_of({4}, col)
[{2,3,4},{4,5,6,7}]

Answer 1

在一般情况下，不会，除了暴力搜索方法。

但是，根据您拥有的数据类型，可以使用多种技术进行线性时间搜索。例如，如果元素值总是小于 32(或 64)，那么您可以创建一个整数，其中包含为当前值设置的位，并对它们进行 OR 以查明该集合是否是一个子集。如果值小于 1 亿左右，您可以创建一个巨大的 bool 数组，其中如果集合包含该值，则每个数组元素为 1，否则为 0。那么子集查找是线性时间的。类似的方法可以解决线性时间内的超集问题。