Wie füge ich Listen mit überlappenden Elementen mithilfe der Graphentheorie zusammen?

Listen mit gemeinsamen Elementen zusammenführen: Ein graphentheoretischer Ansatz

Gegeben sei eine Sammlung von Listen, von denen einige überlappende Elemente enthalten, das Ziel besteht darin, sie in einer Reihe von Listen zu konsolidieren, die alle eindeutigen Elemente der ursprünglichen Listen umfassen. Betrachten Sie beispielsweise die folgende Eingabeliste von Listen:

L = [['a', 'b', 'c'], ['b', 'd', 'e'], ['k'], ['o', 'p'], ['e', 'f'], ['p', 'a'], ['d', 'g']]

Die Aufgabe besteht darin, Listen mit gemeinsamen Elementen zusammenzuführen, bis keine Listen mehr kombiniert werden können. Die gewünschte Ausgabe wäre:

L = [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'o', 'p'], ['k']]

Während boolesche Operationen und While-Schleifen verwendet werden könnten, kann ein effizienterer Ansatz gefunden werden, indem die Listen als Diagramm angezeigt werden. In einer Diagrammdarstellung entspricht jede Liste einer Menge von Knoten, die durch Kanten verbunden sind. Daher besteht das Problem darin, die verbundenen Komponenten in diesem Diagramm zu finden.

Eine Lösung besteht darin, NetworkX zu verwenden, eine robuste Bibliothek für die Diagrammanalyse, wie unten gezeigt:

<code class="python">import networkx 
from networkx.algorithms.components.connected import connected_components

def to_graph(l):
    G = networkx.Graph()
    for part in l:
        # each sublist is a bunch of nodes
        G.add_nodes_from(part)
        # it also imlies a number of edges:
        G.add_edges_from(to_edges(part))
    return G

def to_edges(l):
    """ 
        treat `l` as a Graph and returns it's edges 
        to_edges(['a','b','c','d']) -> [(a,b), (b,c),(c,d)]
    """
    it = iter(l)
    last = next(it)

    for current in it:
        yield last, current
        last = current    

G = to_graph(l)
print(connected_components(G))
# prints [['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]</code>

Durch die Nutzung der Leistung der Graphentheorie erledigt NetworkX die Aufgabe effektiv und stellt Korrektheit und Effizienz sicher.

Das obige ist der detaillierte Inhalt vonWie füge ich Listen mit überlappenden Elementen mithilfe der Graphentheorie zusammen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!