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.
ds.algorithms
sorting
permutations
edit-distance
emchristiansen
quelle
quelle
Antworten:
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.
quelle