Geben Sie n Tupel an und schreiben Sie eine Funktion, die eine Liste mit verbundenen Werten zurückgibt.
Beispiel:
%Vor%Ergebnis:
%Vor%Ich glaube, es könnte mit Hilfe von Graphen oder Bäumen als Datenstruktur gelöst werden, indem Knoten für jeden Wert und Kanten für jedes Paar erstellt werden, wobei jeder Baum oder Graph verbundene Werte darstellt, aber ich habe noch keine Lösung gefunden.
>Was wäre der beste Weg, um in Python ein Ergebnis zu erzeugen, das eine Liste von verbundenen Werten für diese Paare liefert?
Ich wusste nicht, dass dieses Problem bereits einen Namen hatte (danke Avim!), also ging ich voran und löste es naiv.
Diese Lösung ähnelt der von Eli Rose. Ich habe mich jedoch dafür entschieden, es zu posten, weil es für große Listen von Paaren etwas effizienter ist, weil das lists_by_element - Wörterbuch die Liste eines Elements verfolgt, so dass wir es vermeiden können, alle Listen zu durchlaufen ihre Artikel jedes Mal, wenn wir einen neuen Artikel hinzufügen müssen.
Hier ist der Code:
%Vor%Und so funktioniert es: Ссылка
Sie können es mit der Implementierung Disjoint Set (Union-Find) lösen.
Initialisiere die Struktur djs mit allen Zahlen. Dann rufen Sie für jedes Tupel (x,y) djs.merge(x,y) auf. Erstellen Sie nun für jede Zahl x einen neuen Satz für iff djs.sameSet(x,)==false für eine beliebige y von jeder vorhandenen Menge.
Vielleicht das könnte Ihnen helfen.
Eine andere Lösung, die kompakter ist als die von wOlf, aber Griffe verschmelzen im Gegensatz zu Eli:
%Vor% Beachten Sie, dass ich beim Auffinden von Elementen in einer Komponente auf das Aufbrechen von Schleifen angewiesen bin, um mit der else -Klausel der Schleife den Fall zu behandeln, in dem sich die Elemente noch nicht in einer Komponente befinden (% co_de) % wird ausgeführt, wenn die Schleife ohne else ) beendet wurde.
Es sieht so aus, als hätten Sie eine Grafik (in Form einer Liste von Kanten), die möglicherweise nicht alle aus einem Stück ("verbunden") besteht und Sie in Teile ("Komponenten") aufteilen möchten.
Sobald wir darüber in der Sprache der Graphen nachdenken, sind wir meistens fertig. Wir können eine Liste aller bisher gefundenen Komponenten führen (dies sind Sets von Knoten) und einen Knoten zum Satz hinzufügen, wenn sein Partner bereits dort ist. Erstellen Sie andernfalls eine neue Komponente für dieses Paar.
%Vor% Ich habe die seltsame for ... else -Konstruktion benutzt, um diese eine Funktion zu machen - die else wird ausgeführt, wenn eine break -Anweisung während der for nicht erreicht wurde. Die innere Schleife könnte genauso gut eine Funktion sein, die True oder False zurückgibt.
EDIT: Wie Francis Colas betont, ist dieser Ansatz zu gierig. Hier ist ein ganz anderer Ansatz (vielen Dank an Edward Mann für dies schöne DFS-Implementierung).
Dieser Ansatz basiert auf dem Konstruieren eines Graphen und dem Durchführen von Traversierungen darauf, bis uns die nicht besuchten Knoten ausgehen. Es sollte in linearer Zeit laufen (O (n), um den Graphen zu konstruieren, O (n) um alle Durchquerungen zu machen, und ich glaube, dass O (n) nur die eingestellte Differenz macht).
%Vor%Tags und Links python data-structures graph