Sortierung Array in der minimalen Anzahl von Zügen

Question

Es ist theoretisch möglich, ein Array in 10 Moves zu sortieren, indem nur Elemente verschoben werden, die nicht bereits in sortierter Reihenfolge sind.

Wenn die einzige erlaubte Operation eine In-Place-Verschiebung ist, indem Sie ein Element aus Index A entfernen und es in Index B einfügen, ein Element nach dem anderen, wie würden Sie die richtigen Bewegungen erzeugen, um mit dem sortierten Array zu enden? Auch hier sollte Bewegungen erforderlich sein.

Zum Beispiel, hier ist ein Array:

[ 1, 8, 5, 2, 4, 6, 3, 9, 7, 10 ] 

Die längste aufsteigende Teilfolge ist:

[ 1, 2, 4, 6, 7, 10 ] 

Die Indizes dieser Elemente sind:

[ 0, 3, 4, 5, 8, 9 ] 

So werden die Indizes Wir müssen umziehen sind:

[ 1, 2, 6, 7] 

da dies die Indizes sind, die nicht bereits in sortierter Reihenfolge sind.

Um mit einem sortierten Array, um am Ende, die letzten Indizes jener 4 Elemente sind:

[ 7, 4, 2, 8] 

So müssen wir gleichzeitig Index 1 bis Index 7, Index 2 zu indizieren 4 bewegen, index 6 zu Index 2 und Index 7 zu Index 8. Das Problem ist, dass wenn ein Element verschoben wird, die anderen Elemente verschoben werden, wodurch die späteren Verschiebeoperationen ungültig werden. Ich habe versucht, diese Indizes zu transformieren, aber bis jetzt habe ich noch nicht die richtige Liste von Moves gefunden. Irgendwelche Ideen?

Hoffentlich habe ich das Problem gut genug erklärt. Bitte stellen Sie Fragen und ich werde klären. Vielen Dank!

Answer 1

Ihr Problem ist, dass die Quellpositionen in der vorherigen Reihenfolge ausgedrückt werden, während die Zielpositionen in der endgültigen Reihenfolge sind. Wenn Sie 1-> 7 tun, wissen Sie noch nicht, wo 7 in der vorherigen Reihenfolge ist. Sie müssen Anpassungen für alle Züge vornehmen.

Die ursprünglichen Bewegungen sind:

from: [ 1, 2, 6, 7] 
to: [ 7, 4, 2, 8] 

Schritt 1

die Positionen ersten TRANFORM Lassen Sie uns, als ob wir alle Elemente zunächst die Elemente an den neuen Positionen eingesetzt wird, dann wurden zu entfernen. Für die Positionen from gehen Sie von links vor: Entfernen in 1 Schaltpositionen (2,6,7) bis (1,5,6). Das Entfernen bei 1 verschiebt sich wieder (5,6) nach unten (4,5). Entfernen bei 5 verschiebt die 5 auf 4 herunter. Für jede Position in from müssen alle nachfolgenden Positionen mit einem größeren oder gleichen Index dekrementiert werden. Wir erhalten:

from: [ 1, 1, 4, 4] 

Für die to Positionen, gehen vom Ende: Position 8 korrekt ist. Position 2 ist ebenfalls korrekt, aber es bedeutet, dass der Prior (7,4) zum Zeitpunkt des Einfügens tatsächlich (6,3) war. Also passen wir sie an. Ähnlich bedeutet das Einfügen bei 3, dass die vorherige Position 6 bei 5 lag.

So gehen wir für das to Array vom Ende aus, für jede Position dekrementieren wir alle früheren Positionen, die einen größeren Index haben. Die to Array wird:

to: [ 5, 3, 2, 8] 

Schritt 2

Was wir haben, ist die richtige Position für 4 von 4 Einfügungen gefolgt Umzüge. Jetzt wollen wir die Entfernungen und die Einfügungen verschachteln.

Das Einfügen bei 5 muss vor dem Entfernen bei (1, 1, 4) erfolgen. 5 ist größer als jeder von diesen, so dass es die Positionen (1, 1, 4) nicht beeinflusst, aber die 5 ist betroffen, da die 3 Entfernungen links vom Einfügepunkt vorgenommen werden. 5 wird 8.

Die Einfügung bei 3 muss vor der Entnahme bei (4, 4) erfolgen. Da 3 kleiner als die 4 ist, wird die Position 3 von den Entfernungen nicht beeinflusst, aber die Entfernungen müssen auf Positionen (5, 5) erhöht werden.

Insertion bei 2 kommt vor der letzten Entfernung bei 5 (war 4). Es ist kleiner, damit die 5 bis 6

Allgemeine Verfahren für Schritt 2 eingestellt wird:

for i = 0 to size-1 
    for j = size-1 to i+1 
     if from[j] < to[i] then increment to[i] 
     else increment from[j] 

sollten wir die Arrays erhalten:

from: [ 1, 1, 5, 6] 
to: [ 8, 3, 2, 8] 

Diese die letzten Züge sind mit auszuführen die korrekten Positionen zum Zeitpunkt des Umzugs. Die Züge können von links nach rechts gelesen werden: Entfernen bei 1, Einfügen bei 8. Entfernen bei 1, Einfügen bei 3. Entfernen bei 5, Einfügen bei 2. Entfernen bei 6, Einfügen bei 8.