如何从Python中的列表中删除超集列表？

Question

我在Python中有一个列表，如下所示：

[[1,2,3],[2,3],[2,4,3],[4,5],[5]]

我希望删除另一个内部列表的所有内部列表，这些内部列表是一个超集(包含另一个列表的所有元素，但包含其他元素的列表)。对于上面的例子，删除超集应该会产生以下结果：

[[2,3],[5]]

我怎样才能做到这一点？

Answer 1

如果集合较小，则它只能是另一个子集，因此，通过按升序对集合进行迭代，我们可以根据以前找到的最小子集来检查每个元素，以确定它是否是最小子集。

def get_minimal_subsets(sets):
    sets = sorted(map(set, sets), key=len)
    minimal_subsets = []
    for s in sets:
        if not any(minimal_subset.issubset(s) for minimal_subset in minimal_subsets):
            minimal_subsets.append(s)

    return minimal_subsets

l = [[1,2,3],[2,3],[2,4,3],[4,5],[5]]

print(get_minimal_subsets(l))  # [{5}, {2, 3}]

Answer 2

您可以使用列表理解：

d = [[1,2,3],[2,3],[2,4,3],[4,5],[5]]
new_d = [i for i in d if not any(all(c in i for c in b) and len(b) < len(i) for b in d)]

输出：

[[2, 3], [5]]

Answer 3

最后，我得到了@Olivier Melan on的相同想法。您可以使用升序丢弃子集，并在O(n^2) *O(子集计算)中运行。

input = [[1,2,3],[2,3],[2,4,3],[4,5],[5]]
sets = [set(x) for x in input]
sets.sort(key=len)

subsets = []
while sets != []:
    cur = sets[0]
    subsets.append(cur)
    sets = [x for x in sets[1:] if not cur <= x]

output = [list(x) for x in subsets]
print(output)