假设您对所有输入集进行标记。
A={1, 2, 3}, B={1, 2}, C={2, 3}, D={2, 4}, E={}
现在建立中间集合，每个集合对应于宇宙中的一个元素，其中包含其出现的集合的标签：
1={A,B}
2={A,B,C,D}
3={A,C}
4={D}
现在，对于每个输入集合，计算其元素标签集的交集：
For A, {A,B} intesect {A,B,C,D} intersect {A,C} = {A} (*)
如果交集中包含除了集合本身的标签，那么它是该集合的子集。这里没有其他元素，所以答案是否定的。但是，
For C, {A,B,C,D} intersect {A,C} = {A,C}, which means that it's a subset of A.
这种方法的成本取决于集合的实现方式。假设为位图（如您所示）。 假设有n个最大大小为m的输入集和宇宙中的| U |项。 然后，中间集合构造会生成| U |个大小为n位的集合，因此初始化它们需要O（| U | n）的时间。 设置这些位需要O（nm）的时间。 如上所述，在
（*）处计算每个交集需要O（mn）; 所有内容均为O（mn ^ 2）。
将所有这些组合在一起，我们有O（| U | n）+ O（nm）+ O（mn ^ 2）= O（| U | n + mn ^ 2）。使用相同的约定，“all pairs”算法的复杂度为O（|U| ^ 2 n ^ 2）。由于m <= |U|，因此该算法在渐近意义下更快。在实践中也可能更快，因为没有繁琐的簿记来添加常数因子。
附加：在线版本
OP问是否有此算法的在线版本，即可以在逐个到达输入集时增量地维护最大集合的集合。答案似乎是肯定的。中间集合告诉我们新集合是否是已经看到的某个集合的子集。但如何快速确定它是否是一个超集？如果是，又是哪些现有的最大集合？因为在这种情况下，这些最大集合不再是最大的，并且必须被新集合替换。
关键是注意到A是B的超集，当且仅当A'是B'的子集（倾斜符号表示集合补）。
按照这个灵感，我们像以前一样维护中间集。当一个新的输入集S到达时，请执行与上述描述相同的测试：让I（e）是输入元素e的中间集。然后进行此测试
For X = \intersect_{e \in S} . I(e), |X| > 0
（在这种情况下，它大于1而不是像上面那样大于0，因为S还没有出现在I中。）如果测试成功，则新集合是现有最大集合的（可能是不适当的）子集，因此可以丢弃它。
否则，我们必须将S添加为一个新的最大集合，但在执行此操作之前，请计算：
Y = \intersect_{e \in S'} . I'(e) = ( \union_{e \in S'} . I(e) )'
再次提醒，这里的撇号表示补集。并集形式可能更快计算。Y包含已被S取代的极大集合。它们必须从最大集合和I中删除。最后将S作为一个极大集合添加，并使用S的元素更新I.
让我们通过例子来理解。当A到达时，我们将其添加到I中：
1={A} 2={A} 3={A}
当 B 到达时，我们发现 X = {A} intersect {A} = {A}，因此将 B 丢掉并继续。 对于 C，也是同样的情况。 当 D 到达时，我们发现 X = {A} intersect {} = {}，因此继续执行 Y = I'(1) intersect I'(3) = {} intersect {}。这正确地告诉我们最大集合 A 不包含在 D 中，因此没有什么可以删除。但必须将其添加为新的最大集合，并且 I 变为
1={A} 2={A,D} 3={A} 4={D}
出现 E 不会引起任何变化。现在假设有一个新集合 F={2, 3, 4, 5}，我们发现
X = {A} isect {A,D} isect {A} isect {D} isect {}
所以我们不能抛弃F。继续进行
Y = \intersect_{e in {1}} I'(e) = I'(1) = {D}
这告诉我们D是F的一个子集，因此应该被丢弃，同时添加F，剩下的是
1={A} 2={A,F} 3={A,F} 4={F} 5={F}
计算补集在算法的在线性质下既棘手又美妙。输入补集的宇宙只需要包括到目前为止已经出现的输入元素。中间集合的宇宙仅包含当前最大集合中标记的集合。对于许多输入流，这个集合的大小会随着时间稳定或减少。
希望这对您有所帮助。
摘要
这里使用的主要原则是算法设计中经常出现的一个强大思想：反向映射。每当您发现自己正在进行线性搜索以查找具有给定属性的项时，请考虑从该属性构建映射回项。通常情况下，构建此映射的成本很低，并且它可以大大减少搜索时间。最佳示例是变换映射p[i]，它告诉您数组在排列后i位置上的元素。如果您需要搜索位于给定位置a的项，您必须在p中进行搜索，这是一个线性时间操作。另一方面，一个逆映射pi如pi[p[i]] == i不会比p计算时间长（因此它的成本是“隐藏的”），但是pi[a]可以在常数时间内产生所需结果。
原帖作者的实现方式
import collections
import operator
from functools import reduce
def is_power_of_two(n):
"""Returns True iff n is a power of two. Assumes n > 0."""
return (n & (n - 1)) == 0
def eliminate_subsets(sequence_of_sets):
"""Return a list of the elements of `sequence_of_sets`, removing all
elements that are subsets of other elements. Assumes that each
element is a set or frozenset and that no element is repeated."""
if len(sequence_of_sets) <= 1:
return list(sequence_of_sets)
if not isinstance(sequence_of_sets, collections.Sequence):
sequence_of_sets = list(sequence_of_sets)
sets_containing_element = {}
for i, s in enumerate(sequence_of_sets):
for element in s:
try:
sets_containing_element[element] |= 1 << i
except KeyError:
sets_containing_element[element] = 1 << i
out = [s for s in sequence_of_sets
if s and is_power_of_two(reduce(
operator.and_, (sets_containing_element[x] for x in s)))]
return out
