effiziente Art Union der Sätze zur Bestimmung

Question

Ich habe eine (sehr groß) Liste von Sätzen, Wertepaare enthält, wie:

SetList = [{1,2},{2,3},{4,5},{5,6},{1,7}] 

Ich mag effizient die Sätze von Werten bestimmen, die disjunkt wie es sich aus der Transitivität der Beziehungen in den obigen Paaren ergibt. Zum Beispiel ist 1 mit 2 assoziiert, und 2 mit 3 und so sind 1,2,3 assoziiert. Ähnlich ist 1 mit 7 assoziiert, also sind 1,2,3 und 7 assoziiert. Im obigen sind 4, 5 und 6 zugeordnet, aber nicht mit den übrigen Werten. Das Ergebnis sollte wie folgt aussehen:

DisjointSets = [{1,2,3,7},{4,5,6}] 

Gibt es einfache und effiziente Möglichkeit, diese Operation auszuführen, die ich vermisse? Vielen Dank!

Answer 1

Konvertieren von meiner ursprünglichen Liste Tupeln:

TupleList = [(1,2),(2,3),(4,5),(5,6),(1,7)] 

I verwenden NetworkX über (Danke @ user2357112):

import networkx as nx 
G = nx.path_graph(0) 
G.add_edges_from(TupleList) 
DisjointSets = list(nx.connected_components(G)) 

Ist dies der effizienteste Weg, um das Problem zu lösen? Irgendwelche anderen Ideen?

Answer 2

Der Graph Ansatz ist wahrscheinlich schneller als Rekursion, aber für die Interessenten in reinem Python:

def get_disjoints(lst): 
    """Return disjoints.""" 
    def rec_disjoints(lst): 
     if not lst: 
      return disjoints 
     else: 
      chosen = lst[0] 
      # Iterat/Mutate list trick using indicies 
      for i, s in reversed(list(enumerate(lst[:]))): 
       if not chosen.isdisjoint(s): 
        chosen.update(s) 
        del lst[i] 
     disjoints.append(chosen) 
     return rec_disjoints(lst) 

    disjoints = [] 
    return rec_disjoints(lst) 

lst = [{1,2}, {2,3}, {4,5}, {5,6}, {1,7}] 
get_disjoints(lst) 
# [{1, 2, 3, 7}, {4, 5, 6}] 

Dies nutzt die hilfreich isdisjoint Methode für Sätze. Obwohl Iteration + Funktionsaufrufe + Rekursion die Leistung reduzieren.

Hier sind Tests für Robustheit, anwendbar für andere Mitwirkende:

import nose.tools as nt 

def test_disjoint(f): 
    "Verify the test function generates expected disjoints." 
    def verify(lst1, lst2): 
     actual, expected = lst1, lst2 
     nt.eq_(actual, expected) 

    verify(f([{1,2}, {2,3}, {4,5}, {5,6}, {1,7}]), 
      [{1,2,3,7}, {4,5,6}]) 
    verify(f([{4,5}, {5,6}, {1,7}]), 
      [{4,5,6}, {1,7}]) 
    verify(f([{1,7}]), 
      [{1,7}]) 
    verify(f([{1,2}, {2,3}, {4,5}, {5,6}, {1,7}, {10, 11}]), 
      [{1,2,3,7}, {4,5,6}, {10,11}]) 
    verify(f([{4,5}, {5,6}, {1,7}, {10, 11}]), 
      [{4,5,6}, {1,7}, {10,11}]) 
    verify(f([{1,2}, {4,5}, {6,7}]), 
      [{1,2}, {4,5}, {6,7}]) 


test_disjoint(f=get_disjoints)