Also hier ist, was ich tun möchte: Ich habe eine Liste, die mehrere Äquivalenzrelationen enthält:
%Vor%Und ich möchte die Sets zusammenführen, die ein Element teilen. Hier ist eine Beispielimplementierung:
%Vor%Und es druckt
%Vor%Das macht das Richtige, ist aber viel zu langsam, wenn die Äquivalenzrelationen zu groß sind. Ich habe die Beschreibungen zum union-find-Algorithmus nachgeschlagen: Ссылка aber ich habe immer noch Probleme bei der Programmierung einer Python-Implementierung.
O(n) time indices_dict gibt eine Karte von einer Äquivalenz # zu einem Index in lis . Z.B. 1 wird dem Index 0 und 4 in lis zugeordnet.
disjoint_indices gibt eine Liste von disjunkten Indexsätzen. Jeder Satz entspricht Indizes in einer Äquivalenz. Z.B. lis[0] und lis[3] haben die gleiche Äquivalenz, aber nicht lis[2] .
disjoint_set konvertiert disjunkte Indizes in ihre richtigen Äquivalenzen.
Die Komplexität von O(n) ist schwer zu erkennen, aber ich versuche es zu erklären. Hier verwende ich n = len(lis) .
indices_dict läuft sicherlich in O(n) time, weil nur 1 for-Schleife
disjoint_indices ist am schwersten zu sehen. Es läuft sicherlich in O(len(d)) time, da die äußere Schleife stoppt, wenn d leer ist und die innere Schleife ein Element d jeder Iteration entfernt. jetzt ist die len(d) <= 2n seit d eine Karte von Äquivalenz # zu Indizes und es gibt höchstens 2n unterschiedliche Äquivalenz # in lis . Daher wird die Funktion in O(n) ausgeführt.
disjoint_sets ist wegen der 3 kombinierten For-Schleifen nur schwer zu erkennen. Sie werden jedoch feststellen, dass höchstens i über alle n Indizes in lis und x über das 2-Tupel laufen kann, so dass die Gesamtkomplexität 2n = O(n)
Tags und Links python list union-find