假设您标记所有输入集。
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)。使用相同的约定，您的“所有对”算法为 O(|U|^2 n^2)。由于 m <= |U|，该算法渐近地更快。它在实践中也可能更快，因为没有复杂的簿记来添加常数因子。
补充：在线版
OP 询问是否有该算法的在线版本，即当输入集一个接一个到达时，最大集合的集合可以增量维护。答案似乎是肯定的。中间集可以快速告诉我们一个新集是否是已经见过的集的子集。但是如何快速判断它是否是超集？如果是这样，哪些现有的最大集合？因为在这种情况下，那些最大集合不再是最大的，必须用新的集合来代替。
关键是要注意iffA的超集是（勾号'表示集合补码）的子集。BA'B'
遵循这个灵感，我们像以前一样保持中间集。当一个新的输入集S到达时，进行与上述相同的测试：设I(e)为输入元素的中间集e。那么这个测试是
For X = \intersect_{e \in S} . I(e), |X| > 0
（在这种情况下，它大于零而不是上面的一，因为它还S没有进入I。）如果测试成功，那么新集合是现有最大集合的（可能不正确的）子集，因此可以丢弃它。
否则，我们必须添加S一个新的最大集，但在此之前，计算：
Y = \intersect_{e \in S'} . I'(e) = ( \union_{e \in S'} . I(e) )'
再次将勾号'设置为补码。联合形式的计算速度可能会快一些。Y包含已被 取代的最大集合S。它们必须从最大集合和I. 最后添加S为最大集并I使用S' 元素进行更新。
让我们来看看我们的例子。到达时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，a线性时间操作。另一方面，一个逆映射不需要比实际计算时间更长（pi因此它的成本是“隐藏的”），但是pi[p[i]] == ippi[a]在恒定时间内产生所需的结果。
由原始海报实施
import collections
import operator
from functools import reduce # only in Python 3
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."""
# The code below does not handle the case of a sequence containing
# only the empty set, so let's just handle all easy cases now.
if len(sequence_of_sets) <= 1:
return list(sequence_of_sets)
# We need an indexable sequence so that we can use a bitmap to
# represent each set.
if not isinstance(sequence_of_sets, collections.Sequence):
sequence_of_sets = list(sequence_of_sets)
# For each element, construct the list of all sets containing that
# element.
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
# For each set, if the intersection of all of the lists in which it is
# contained has length != 1, this set can be eliminated.
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