在集合中寻找子集和超集的有效方法

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亿左右，您可以创建一个巨大的布尔数组，其中如果集合包含值，则每个数组元素为1，如果不包含值，则为0。那么子集查找是线性时间。对于线性时间内的超集问题，类似的方法也是可能的。

Answer 2

您可以为子集创建哈希方法，然后将其存储在HashMap中。

那么你甚至可以在固定的时间内找到它(如果你有足够的内存)。