Minimalna liczba transpozycji do sortowania listy

Próbując opracować własny algorytm sortowania, szukam optymalnego testu porównawczego, z którym mogę go porównać. W przypadku nieposortowanego uporządkowania elementów A i posortowanego uporządkowania B , jaki jest skuteczny sposób obliczenia optymalnej liczby transpozycji, które można uzyskać od A do B ?

Transpozycja jest definiowana jako zmiana pozycji 2 elementów na liście, a więc na przykład

1 2 4 3

ma jedną transpozycję (transpozycja 4 i 3), aby to zrobić

1 2 3 4

Coś jak

1 7 2 5 9 6

wymaga 4 transpozycji (7, 2), (7, 6), (6,5), (9, 7)

Aktualizacja (9.7.11): zmieniono pytanie, aby używać „transpozycji” zamiast „swapów” w odniesieniu do niesąsiadujących giełd.

ds.algorithms co.combinatorics sorting sova
źródło

co jeśli możesz po prostu zamienić sąsiadów? jak mogę obliczyć minimalną liczbę zamian?

Odpowiedzi:

Jeśli masz do czynienia tylko z permutacji elementów, to trzeba będzie dokładnie swapy, gdzie jest liczba cykli w rozkładzie cyklu rozłączne z . Ponieważ odległość ta jest niezmienna, przekształcenie w (lub w lub odwrotnie) wymaga takich ruchów. $n$ $n-c(\pi)$ $c(\pi)$ $\pi$ $\pi$ $\sigma$ $A$ $B$ $n-c(\sigma^{-1}\circ\pi)$

Anthony Labarre
źródło

Pomimo głosowania na to dawno temu, po prostu kliknęło dziś. Jak kostka Rubika, prawda: D?

sova

Odległość zamiany może być również izometrycznie osadzona w przestrzeni euklidesowej. Dla każdego łańcucha s zbuduj macierz gdzie jeśli występuje przed a w przeciwnym razie wynosi zero. Zatem odległość Frobeniusa jest odległością wymiany . (ze slajdów Grahama Cormode'a ). Nie tak elegancki jak odpowiedź Anthony'ego, ale dość łatwy do obliczenia. $M(s)$ $M_{ij} = 1$ $i$ $j$ $\|M(s) - M(s')\|^2$ $d(s,s')$

Aktualizacja: zobacz komentarze Oleksandra

Suresh Venkat
źródło

Wydaje mi się, że w prezentacji Grahama oznaczają one normę spektralną (

), a nie normę Frobeniusa (

‖ A ‖_{2}

$\|A\|_2$

‖ A ‖_{F}

$\|A\|_F$

Oleksandr Bondarenko

chociaż jeśli wszystko, co chcesz zrobić, to policzyć różnice, to kwadrat normy frobenius powinien działać dobrze?

Suresh Venkat

co jest oczywiście odległością Hamminga dla matryc 0-1

Suresh Venkat

Masz rację co do równości kwadratu normy Frobeniusa i odległości Hamminga. Chciałbym dodać, że odległość Hamminga podzielona przez

równa się odległości zamiany. Pytanie dotyczyło jednak odległości transpozycji („Zamiana jest definiowana jako zmiana pozycji 2 elementów na liście”), a nie odległości wymiany. Co dotyczy normy widmowej, to jej kwadrat jest równy odległości zamiany.

2

$2$

Oleksandr Bondarenko

Oleksandr: Więc przypuszczam, że interpretujesz „zamianę” jako „wymianę dwóch sąsiednich elementów”?

Anthony Labarre