Найти самый большой вложенный список непересекающихся множеств из исходного вложенного списка

Question

У меня есть следующий вложенный список (только целые числа).

L = [[9, 10, 14, 19, 11], [9, 11, 13, 12, 4], [40, 43, 44, 42, 41, 26, 14], [10, 16, 17, 26, 14], [25, 28, 20], [25, 20, 21, 27, 24], [3, 29, 22, 28], [25, 15, 2, 16, 17, 24], [0, 2, 16, 10, 9, 4], [0, 1, 29, 3], [29, 31, 32, 23, 22], [29, 31, 33, 8, 51, 1], [0, 1, 51, 50, 49, 39, 12, 4], [0, 2, 15, 3], [25, 15, 3, 28]]

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

[[9, 11, 13, 12, 4], [40, 43, 44, 42, 41, 26, 14], [25, 20, 21, 27, 24], [3, 29, 22, 28], [0, 1, 51, 50, 49, 39, 12, 4]]

Я не уверен, как поступить. Любая помощь будет принята с благодарностью.

Большое спасибо.

Answer 1

По сути, это проблема графа. Каждый подсписок является узлом, и между ними есть грань, если они не пересекаются. Мы хотим найти самые большие клики, то есть подграфы, где все пары узлов связаны. Это NP-полная проблема, так что если L становится большим, это займет некоторое время.

from networkx import Graph, find_cliques
from itertools import combinations, takewhile

L = [[9, 10, 14, 19, 11], [9, 11, 13, 12, 4], [40, 43, 44, 42, 41, 26, 14], [10, 16, 17, 26, 14], [25, 28, 20],
     [25, 20, 21, 27, 24], [3, 29, 22, 28], [25, 15, 2, 16, 17, 24], [0, 2, 16, 10, 9, 4], [0, 1, 29, 3],
     [29, 31, 32, 23, 22], [29, 31, 33, 8, 51, 1], [0, 1, 51, 50, 49, 39, 12, 4], [0, 2, 15, 3], [25, 15, 3, 28]]

L = map(tuple, L)

g = Graph()
g.add_nodes_from(L)

for sublist1, sublist2 in combinations(L, 2):
    if set(sublist1).isdisjoint(sublist2):
        g.add_edge(sublist1, sublist2)

cliques = sorted(find_cliques(g), key=len, reverse=True)
cliques = list(takewhile(lambda c: len(c) == len(cliques[0]), cliques))
for clique in cliques:
    flat = sum(clique, ())
    assert len(flat) == len(set(flat))
    print(sorted(flat))
    print(sorted(clique))

Выход:

[0, 1, 2, 3, 4, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 20, 25, 26, 28, 29, 31, 33, 51]
[(0, 2, 15, 3), (9, 11, 13, 12, 4), (10, 16, 17, 26, 14), (25, 28, 20), (29, 31, 33, 8, 51, 1)]
[0, 2, 3, 4, 9, 10, 11, 12, 13, 14, 15, 16, 17, 20, 22, 23, 25, 26, 28, 29, 31, 32]
[(0, 2, 15, 3), (9, 11, 13, 12, 4), (10, 16, 17, 26, 14), (25, 28, 20), (29, 31, 32, 23, 22)]
[0, 1, 2, 3, 4, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 24, 25, 26, 27, 29, 31, 33, 51]
[(0, 2, 15, 3), (9, 11, 13, 12, 4), (10, 16, 17, 26, 14), (25, 20, 21, 27, 24), (29, 31, 33, 8, 51, 1)]
[0, 2, 3, 4, 9, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 27, 29, 31, 32]
[(0, 2, 15, 3), (9, 11, 13, 12, 4), (10, 16, 17, 26, 14), (25, 20, 21, 27, 24), (29, 31, 32, 23, 22)]
[0, 1, 2, 3, 4, 8, 9, 11, 12, 13, 14, 15, 20, 25, 26, 28, 29, 31, 33, 40, 41, 42, 43, 44, 51]
[(0, 2, 15, 3), (9, 11, 13, 12, 4), (25, 28, 20), (29, 31, 33, 8, 51, 1), (40, 43, 44, 42, 41, 26, 14)]
[0, 1, 2, 3, 4, 8, 9, 11, 12, 13, 14, 15, 20, 21, 24, 25, 26, 27, 29, 31, 33, 40, 41, 42, 43, 44, 51]
[(0, 2, 15, 3), (9, 11, 13, 12, 4), (25, 20, 21, 27, 24), (29, 31, 33, 8, 51, 1), (40, 43, 44, 42, 41, 26, 14)]
[0, 2, 3, 4, 9, 11, 12, 13, 14, 15, 20, 22, 23, 25, 26, 28, 29, 31, 32, 40, 41, 42, 43, 44]
[(0, 2, 15, 3), (9, 11, 13, 12, 4), (25, 28, 20), (29, 31, 32, 23, 22), (40, 43, 44, 42, 41, 26, 14)]
[0, 2, 3, 4, 9, 11, 12, 13, 14, 15, 20, 21, 22, 23, 24, 25, 26, 27, 29, 31, 32, 40, 41, 42, 43, 44]
[(0, 2, 15, 3), (9, 11, 13, 12, 4), (25, 20, 21, 27, 24), (29, 31, 32, 23, 22), (40, 43, 44, 42, 41, 26, 14)]

Вывод выполняется парами: сначала плоский список, затем 2D-список.