Как вы можете удалить списки надмножеств из списка списков в Python?

Question

У меня есть список списков в Python, подобный следующему:

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

Я хочу удалить все внутренние списки, которые являются надмножеством (список, который содержит все элементы другого списка, но сдополнительные элементы) другого внутреннего списка.В приведенном выше примере удаление надмножеств должно привести к следующему:

[[2,3],[5]]

Как мне это сделать?

Answer 1

Вот оно:

super=[[1,2,3],[2,3],[2,4,3],[4,5],[5]]
subset=[s for s in super if not any(set(s).issuperset(set(i)) and len(s)>len(i) for i in super)]

Вывод:

>>> subset
[[2, 3], [5]]

Answer 2

Набор может быть только подмножеством другого, если он меньше, поэтому, перебирая наборы в порядке возрастания размера, мы можем проверить каждый элемент по найденным ранее минимальным подмножествам, чтобы узнать, является ли он минимальным подмножеством.

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 3

У меня появилась та же идея, что и у Оливье Мелансона.Вы можете использовать возрастающий порядок, чтобы отбросить подмножества и выполнить этот прогон в 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)

Answer 4

Вы можете использовать понимание списка:

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]]