Finde die größte verschachtelte Liste von sich nicht überschneidenden Mengen aus einer ursprünglichen verschachtelten Liste

Question

Ich habe die folgende verschachtelte Liste (nur ganze Zahlen).

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

Ich möchte eine verschachtelte Liste, welche Gruppen die größte Menge an nicht-schneidende Sätze von der ursprünglichen verschachtelten Liste (oben) kommt zu finden. Die Ausgabe wäre etwas wie:

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

Ich bin mir nicht sicher, wie es weiter geht. Jede Hilfe würde sehr geschätzt werden.

Vielen Dank.

Answer 1

Dies ist im Wesentlichen ein Grafikproblem. Jede Unterliste ist ein Knoten und es gibt eine Kante zwischen ihnen, wenn sie nicht zusammenhängen. Wir wollen find the biggest cliques, d.h. Untergraphen, wo alle Paare Knoten verbunden sind. Dies ist ein NP-vollständiges Problem, wenn also L groß wird, wird dies eine Weile dauern.

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

Output:

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

Der Ausgang paarweise ist: zuerst die abgeflachte Liste aus, und die 2D-Liste.