从原始嵌套列表中查找非相交集的最大嵌套列表

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 列表。