Effizientes Finden der Mindestanzahl von Transpositionen, die zum Sortieren einer Liste erforderlich sind

8

Ich möchte eine effiziente Methode zur Berechnung der Mindestanzahl von Transpositionen, die zum Sortieren einer Liste erforderlich sind. Ich muss nicht wissen, was die Transpositionen tatsächlich sind.

Zum Beispiel erfordert die Liste [1, 1, 2, 0] 2 Transpositionen:

[1, 1, 2, 0] // Start
[1, 1, 0, 2] // Swap index 2 and 3
[0, 1, 1, 2] // Swap index 0 and 2

Die Liste [0, 1, 0, 0] erfordert 1 Umsetzung:

[0, 1, 0, 0] // Start
[0, 0, 0, 1] // Swap index 1 and 3

Die Liste [2, 2, 2, 2] erfordert 0 Transpositionen, da sie bereits sortiert ist.

Einige Metainformationen: 1) Die Liste enthält möglicherweise wiederholte Elemente, sodass die einfache Verwendung des Cayley-Abstands zwischen der Sortierung und der Identitätspermutation nicht funktioniert . 2) Diese Frage zum mathematischen Überlauf ist verwandt.

emchristiansen
quelle
1
Ich denke, dass die hier veröffentlichten Antworten zu Frage 4096 zusammengeführt werden sollten.
Tsuyoshi Ito
1
@derekhh, dies ist kein Duplikat (oder zumindest ist die Interpretation des Beitrags in der anderen Frage anders). Ich habe im ursprünglichen Beitrag auf Frage 4096 verlinkt.
Emchristiansen
3
Frage 4096 besagt nicht, dass bestimmte Elemente unterschiedlich sind. Leider haben alle dort veröffentlichten Antworten dies stillschweigend angenommen, und dieses Versehen kann korrigiert werden, indem die Antwort (en) hier und dort zusammengeführt werden.
Tsuyoshi Ito
1
@ emchristiansen Ups, sorry, ich habe das nicht bemerkt ...
derekhh

Antworten:

7

Leider ist das Problem laut Amir, Hartman, Kapah, Levy und Porat (siehe http://epubs.siam.org/doi/abs/10.1137/080712969 ) im Allgemeinen NP-schwer , selbst wenn jedes Symbol höchstens erscheint drei Mal. Ich fand keine Erwähnung eines Algorithmus zur Annäherung an konstante Faktoren oder von etwas, das ziemlich schnell ist, um das Problem anzugehen. Gibt es zusätzliche Einschränkungen, an die Sie in Ihrem Fall denken können?

EDIT: Die Autoren geben auch einen 3/2-Approximationsalgorithmus an, aber ich weiß nicht, ob er für Ihre Zwecke gut genug ist.

Anthony Labarre
quelle
Danke für den Hinweis. Ich habe es mit Pixelwerten zu tun, also Listen mit ganzen Zahlen in [0, 255]. Eine übliche Listenlänge beträgt 256 Elemente.
Emchristiansen
Können Sie beweisen, dass Sie bei einer Lösung (minimale Sortierfolge der Transposition) immer eine große Zahl links gegen eine kleinere Zahl rechts austauschen?
Ivan Kuckir