Minimale Anzahl von Transpositionen zum Sortieren einer Liste

Beim Versuch, meinen eigenen Sortieralgorithmus zu entwickeln, suche ich nach dem optimalen Benchmark, mit dem ich ihn vergleichen kann. Was ist ein effizienter Weg, um bei einer unsortierten Anordnung der Elemente A und einer sortierten Anordnung B die optimale Anzahl von Transpositionen zu berechnen, die von A nach B gelangen ?

Eine Transposition ist definiert als das Umschalten der Position von 2 Elementen in der Liste, zum Beispiel

1 2 4 3

hat eine Transposition (Transposition 4 und 3), um es zu machen

1 2 3 4

Etwas wie

1 7 2 5 9 6

erfordert 4 Transpositionen (7, 2), (7, 6), (6,5), (9, 7)

Update (07.09.11): Die Frage wurde dahingehend geändert, dass "Transposition" anstelle von "Swaps" für nicht benachbarte Börsen verwendet wird.

ds.algorithms co.combinatorics sorting sova
quelle

was ist, wenn du nur die Nachbarn tauschen kannst? Wie kann ich die Mindestanzahl von Swaps ermitteln?

Antworten:

Wenn Sie nur mit Permutationen von Elementen arbeiten, benötigen Sie genau Swaps, wobei die Anzahl der Zyklen in der disjunkten Zykluszerlegung von . Da diese Distanz bi-invariant ist, erfordert die Transformation von in (oder von in oder umgekehrt) solche Bewegungen. $n$ $n-c(\pi)$ $c(\pi)$ $\pi$ $\pi$ $\sigma$ $A$ $B$ $n-c(\sigma^{-1}\circ\pi)$

Anthony Labarre
quelle

Obwohl wir schon vor langer Zeit dafür gestimmt haben, hat es heute einfach geklickt. Wie ein Zauberwürfel, richtig: D?

Sova

Der Swap-Abstand kann auch isometrisch in den euklidischen Raum eingebettet werden. Konstruieren Sie für jede Zeichenkette s eine Matrix wobei wenn vor auftritt und andernfalls Null ist. Dann ist der Frobenius-Abstand der Tauschabstand . (aus Graham Cormodes Dias ). Nicht so elegant wie Anthonys Antwort, aber recht einfach zu berechnen. $M(s)$ $M_{ij} = 1$ $i$ $j$ $\|M(s) - M(s')\|^2$ $d(s,s')$

Update: Bitte beachten Sie Oleksandrs Kommentare

Suresh Venkat
quelle

Es scheint mir, dass sie in Grahams Darstellung die spektrale Norm (

) und nicht die Frobenius-Norm (

) bedeuten .

‖ A ‖_{2}

$\|A\|_2$

‖ A ‖_{F}

$\|A\|_F$

Oleksandr Bondarenko

obwohl, wenn Sie nur die Unterschiede zählen möchten, dann sollte das Quadrat der Frobenius-Norm richtig funktionieren?

Suresh Venkat

Das ist natürlich die Hamming-Distanz für 0-1-Matrizen

Suresh Venkat

Sie haben Recht mit der Gleichheit zwischen dem Quadrat der Frobenius-Norm und der Hamming-Distanz. Ich möchte hinzufügen, dass die Hamming-Distanz geteilt durch

gleich der Swap-Distanz ist. Die Frage war jedoch nach der Transpositionsentfernung ("Ein Swap ist definiert als das Umschalten der Position von 2 Elementen in der Liste") und nicht nach der Swap-Entfernung. Was die spektrale Norm betrifft, ist das Quadrat gleich der Swap-Distanz.

2

$2$

Oleksandr Bondarenko

Oleksandr: Also nehme ich an, Sie interpretieren "Tauschen" als "Austausch zweier benachbarter Elemente"?

Anthony Labarre