在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)个集合比较。或者想一想，它可能比直接算法更糟糕，因为你可能会多次检查同一集合。

Answer 2

理解这一点

对于集合列表L，返回L中没有超集的集合

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

和

skt = {{D}, {E,G}, {E,H}, {D,E,F}, {E,F,G}}
out = {{D}, {E,G}, {E,H}, {D,E,F}}

如果这是正确的，那么(在我看来，我可能是错的)最坏的情况总是迫使你检查所有的对。你可以做一些改进，比如不要迭代已经被删除的元素。或者只检查每一对，并在两个方向上都这样做，并相应地更新。itertools.product可能很有用，但同样，它不会自动更新，所以当您删除一个元素时，我不确定什么才是有效的。

更优化的代码可能是：

skt = {frozenset({1}), frozenset({1,2,3}), frozenset({2,3}), frozenset({4}), 
       frozenset({5,7}), frozenset({5,8}), frozenset({5,6,7}), 
       frozenset({6,7,8})}

newset = set()

def check(elem):
    to_delete = []
    ret = True
    for y in skt:
        if elem > y:
            to_delete.append(elem)
            ret = False
            break
        if y > elem:
            to_delete.append(y)
    for d in to_delete:
        skt.remove(d)
    return ret  

while skt:
    checking = skt.pop()
    if check(checking):
        newset.add(checking)

Answer 3

此方法本质上与您的方法相同，但它是按基数递增的顺序运行的。优势可能是显著的，这取决于您的数据(如果有一些小的集合，可以在早期迭代中淘汰许多其他集合)。

from collections import defaultdict

def foo(skt):

    # Index the sets by cardinality
    index = defaultdict(lambda: set())
    for s in skt:
        index[len(s)].add(s)

    # For each cardinality i, starting with the lowest
    for i in range(max(index.keys()) + 1):

        # For each cardinality j > i (because supersets must be larger)
        for j in range(i + 1, max(index.keys()) + 1):

            # Remove j-sized supersets
            for y in [y for y in index[j] if any(y >= x for x in index[i])]:
                index[j].remove(y)

    # Flatten the index
    return set(x for xs in index.values() for x in xs)