python - 仅从python中的集合中选择子集

Question

我正在尝试删除超集(如果我的集合中的任何集合都有超集)并仅返回集合中的子集。我已经编写了以下代码，但由于我正在处理大型数据集，因此执行需要很长时间，有人可以为此建议其他选项。

例如，如果我有一组像这样的卡住集

skt = {{D},{E,D,M},{E,M}}

我需要像

这样的输出

skt = {{D},{E,M}}

我的代码是，

for item in skt.copy():
    for other_item in skt.difference([item]):
        if item >= other_item:
            skt.remove(item)
            break

提前致谢。

Answer 1

至少可以做一个小的优化:不要复制一组，而是创建一个新的:

newset = set()
for x in skt:
   if not any(y < x for y in skt):
      newset.add(x)

或者在一行中:

newset = set(x for x in skt if not any(y < x for y in skt))

更新:

您可以为每个元素预先计算包含该元素的集合的集合，然后仅针对包含至少一个元素的集合检查每个集合:

setsForElement = defaultdict(set);
for s in skt:
    for element in s:
        setsForElement[element].add(s);

newset = set(s for s in skt if not any (setForElement < s for element in s for setForElement in setsForElement[element]))

# last line is equal to:
newset = set();
for s in skt:
    good = True;
    for element in s:
        if any(setForElement < s for setForElement in setsForElement[element]):
            good = False;
            break;

    if good:
        newset.add(s);

这可能会为您节省一些时间，具体取决于您的数据集。当然，在最坏的情况下(例如，如果您的数据集是某个集合的 power set)，复杂度将再次为 O(N^2) 集合比较。或者想想看，它可能比直接算法更糟糕，因为您可能会多次检查同一个集合。