Sei A eine Liste und S eine sortierte Liste der gleichen Elemente. Angenommen, alle Elemente sind unterschiedlich. Wie finde ich einen minimalen Satz von "Moves" ( move X before Y (or end) ), der A in S verwandelt?
Beispiele:
%Vor%Ich bevorzuge Javascript oder Python, aber jede Sprache reicht.
Dieses Problem entspricht dem Problem mit der längsten zunehmenden Untersequenz .
Sie müssen einen Vergleichsoperator less definieren. less(a, b) gibt true nur dann zurück, wenn a vor b in der Zielsequenz steht. Berechnen Sie nun mithilfe dieses Vergleichsoperators die maximal zunehmende Untersequenz der Quellsequenz. Sie müssen jedes Element verschieben, das nicht Teil dieser Untersequenz ist (andernfalls wird die Untersequenz nicht maximal sein) und Sie können es genau einmal verschieben (indem Sie es an seine Zielposition verschieben).
EDIT: Wie von amit verlangt, ist mein Beweis für die obige Aussage:
Bezeichnen wir die Zielsequenz B und bezeichnen wir die Quellsequenz A . Lassen Sie n = |A| und lassen Sie k die Länge der längsten ansteigenden Sequenz sein, wie oben beschrieben.
B von A mit weniger Bewegungen als n - k zu erreichen. Dies bedeutet, dass mindestens n - k + 1 -Elemente aus A nicht verschoben werden. Sei s 1 , s 2 , ... s m die Menge der Elemente, die nicht bewegt werden. Aus der Annahme wissen wir, dass m > k . Da diese Elemente sich nicht bewegt haben, kann sich ihre relative Position zueinander nicht geändert haben. Somit sind die relativen Positionen all dieser Elemente in der Zielsequenz B gleich der in A . Daher sollte der Operator weniger (s i , s j ) wie oben definiert für alle i , j wahr sein. Wenn dies jedoch zutrifft, dann erhöht s 1, s 2, ... s m die Sequenz und als m > k führt dies zu a Widerspruch zu der Annahme, dass k die Länge der am längsten wachsenden Sequenz ist. B von A zu erreichen, indem Sie alle Elemente verschieben, außer denen, die Teil der am längsten wachsenden Sequenz sind. Wir werden die Elemente in der Reihenfolge verschieben, in der sie in B erscheinen. Wir werden keine Elemente verschieben, die Teil der längsten wachsenden Sequenz sind. Wenn das aktuelle Element das erste in B ist, verschieben wir es einfach an den Anfang der Sequenz. Andernfalls verschieben wir das aktuelle Element rechts nach die Position des vorherigen Elements in B. Beachten Sie, dass dieses Element entweder das vorherige Element sein kann, das wir bewegt haben, oder ein Element aus der am längsten wachsenden Sequenz. Beachten Sie, dass bei jedem Schritt, wenn wir das Element mit dem Index i verschieben, alle Elemente mit dem Index 1, 2, ...i-1 bereits die richtigen relativen Positionen zueinander haben. BEARBEITEN: Hinzufügen eines Codes, um die Antwort klarer zu machen. Ich fühle mich nicht als Experte in Javascript, also fühlen Sie sich frei, meine Lösung zu korrigieren oder zu kritisieren.
Definieren wir eine Funktion transform(a, s) , die zwei Parameter benötigt - listet a und b auf, wie in der Anweisung beschrieben. Zuerst erstelle ich eine Karte positions , die jedes Element in a auf seine Position in s abbildet:
Jetzt, da ich dieses Array habe, kann ich eine Hilfsfunktion definieren, die weniger wie in meiner obigen Antwort beschrieben ist. Less nimmt zwei Werte a und b (und die gerade erstellte Helper Map) und gibt true zurück, wenn und nur wenn a vor b in s (die Zielliste) steht:
Nun werde ich nicht beschreiben, wie wir die maximal zunehmende Teilfolge in a in Bezug auf diesen Vergleichsoperator finden können. Sie können sich diese Frage ansehen, um eine detaillierte Erklärung dazu zu erhalten. Ich nehme einfach an, dass ich eine Funktion definiert habe:
Dies gibt die maximal steigende Untersequenz in a in Bezug auf den oben definierten Vergleichsoperator less (unter Verwendung von positions ) als Liste zurück. Ich werde Ihr zweites Beispiel verwenden, um zu veranschaulichen, was wir bisher haben:
Die Werte in Positionen sind wie folgt:
%Vor% Und das Ergebnis von max_increasing_subsequence(a, positions) wird [1, 2, 3] sein. Übrigens, wenn sich Elemente in a wiederholen, ist es möglicherweise besser, Indizes anstelle der Elemente von max_increasing_subsequence zurückzugeben (in diesem speziellen Beispiel ist der Unterschied nicht sichtbar).
Nun werde ich eine weitere Hilfsmaske erstellen, um anzugeben, welche Elemente in der maximal zunehmenden Untersequenz enthalten sind:
%Vor% Nun können Sie die Lösung mit einer einzigen Iteration über s abschließen. Ich werde einen Sonderfall für das letzte Element hinzufügen, um Code leichter verständlich zu machen:
Bitte beachten Sie, dass ich in der obigen Lösung davon ausgehe, dass jedes Mal, wenn Sie einen neuen Befehl protokollieren, Sie ihn in Bezug auf die Reihenfolge des Arrays a protokollieren, nachdem alle vorherigen Befehle ausgeführt wurden.
Insgesamt glaube ich, dass transform so aussehen sollte:
%Vor%Ich hoffe, dieser Code macht meine Antwort klarer.
Wenn Sie Ihre zwei Listen als zwei Strings betrachten - z. Bei den Zahlen handelt es sich um Werte in der ASCII-Codierung. Das Problem entspricht dann dem Auffinden der Operationen, mit denen Sie die erste Zeichenfolge in die zweite umwandeln können. Die Anzahl der Operationen ist wiederum der Levenshtein oder die Entfernung zwischen den Strings.
Die Levenshtein-Distanz kann von dynamische Programmierung verwenden , in einer Matrix die Abstände zwischen allen Präfixen der beiden Strings speichern und dann Ihre Schritte zurückverfolgen, um in jeder Zeile der Matrix zu finden, welche die optimale Operation ist (diejenige, die hat die wenigsten Operationen benötigt, um es zu erreichen).
Der von @IvayloStrandjev vorgeschlagene am längsten zunehmende Subsequenzalgorithmus steht in Zusammenhang mit dem längsten allgemeinen Subsequenzproblem, das wiederum mit der Editierdistanz als einer alternativen Metrik in Beziehung steht, die nur Insertion und Substitution erlaubt. Wahrscheinlich ist es leistungsfähiger im Raum, da es die Tatsache nutzt, dass eine der Sequenzen sortiert werden muss; Ich wollte nur eine alternative Antwort geben, die ich leichter verstehen kann.
Hier ist eine Implementierung in Python des vollständigen Matrix-Levenshtein-Algorithmus, wie er auf der oben verlinkten Wikipedia-Seite beschrieben ist (ursprünglich gefunden in einer 1974 Paper von Wagner und Fischer ), wo auch ein Korrektheitsnachweis zur Verfügung gestellt wird. Hier speichern wir auch die Namen der Operationen in einer Matrix der gleichen Größe wie die Operationen scores , und wir drucken die optimale Operation nach Abschluss einer Zeile.
%Vor%Gehen Sie folgendermaßen vor, um den Code mit den von Ihnen bereitgestellten Beispielen auszuführen, und erwartet die Ausgabe:
%Vor%Dies hängt stark von einigen Parametern des Problems ab, die nicht angegeben sind. Erstens, welche Bewegungen sind legal? Benachbarte Elemente tauschen nur? Beliebige Löschungen und Einfügungen? Zweitens, brauchst du nur die Anzahl der Züge oder brauchst du eine Liste bestimmter Züge? Dies führt zu unterschiedlichen Algorithmen dafür:
Inversionszählungen sind ziemlich einfach und können mit einigen grundlegenden rekursiven Algorithmen durchgeführt werden. Sie können eine Zusammenführungssortierung verwenden, um die Inversionszählung zwischen zwei Listen zu finden, indem Sie eine Liste verwenden, um eine transformierte Version des anderen zu erstellen, wobei die neuen Elemente Indizes sind. Wenn Sie also zwei Sequenzen haben, können Sie Folgendes tun:
%Vor%Eine einfache Python-Misch-Sortierung-Implementierung zum Zählen der Inversionen ist:
%Vor%Dies teilt die Liste nur in zwei Hälften und zählt die Inversionen, sortiert die Liste so wie sie ist. Merge-Sort ist ziemlich effizient, algorithmisch gesprochen (NlogN, obwohl man es praktisch mit ein paar numpigen Matrizen oder durch eine geringfügige Anpassung an den C-Code für den zugrunde liegenden Python-Sortieralgorithmus schneller berechnen könnte. Technisch gesehen, da dieser Ansatz jeden transformiert Typ von Variablen in Zahlen, es ist im Grunde auf nur eine Liste Sortieransatz reduziert, so dass Sie andere Element weise Listenarten verwenden können, um das gleiche zu tun, solange Sie die Anzahl verfolgen.
Mit einer dieser Methoden (Inversionszählung, Levenstein, etc.) können Sie die Züge eindeutig protokollieren. Inversionszählungen protokollieren die Swaps, logc notierte einen vernünftigen Ansatz, um einige allgemeinere Moves für Levenstein zu protokollieren. Persönlich tendiere ich dazu, Inversionszählungen dafür zu verwenden, weil sie ziemlich einfach sind. Aber es kommt sehr darauf an, was du willst. Wenn Sie mehr Operationen als Zwei-Elemente-Nachbar-Swaps benötigen, ist Levenstein eine klare Wahl.
Führe eine Cycle-Sortierung durch und zähle die Anzahl der Züge. Das ist garantiert die Mindestanzahl.
Tags und Links python javascript algorithm language-agnostic