Złożoność zastosowania permutacji w miejscu

Ku mojemu zaskoczeniu nie udało mi się znaleźć artykułów na ten temat - prawdopodobnie przeszukałem niewłaściwe słowa kluczowe.

Mamy więc tablicę czegokolwiek i funkcję na jej indeksach; jest permutacją.$f$$f$

Jak zmienić kolejność tablic zgodnie z pamięcią i czasem działania tak blisko i jak to możliwe?$f$$O(1)$$O(n)$

Czy są jakieś dodatkowe warunki, kiedy zadanie staje się łatwiejsze? Np. Kiedy wyraźnie wiemy, że funkcja jest odwrotnością ?$g$$f$

Znam algorytm, który śledzi cykle i przemierza cykl dla każdego indeksu, aby sprawdzić, czy jest najmniej w swoim cyklu, ale znowu, ma najgorszy czas działania , chociaż średnio wydaje się, że zachowuje się lepiej ...$O(n^2)$

Opcja 0: Permuting In Place (1995) Faith E. Fich, J. Ian Munro, Patricio V. Poblete czas spacja.$O(n \log n)$$O( \log^{2} n )$

Opcja 1: Oszukuj, kompresując swoją permutację do zwięzłej struktury danych, patrz Munro http://www.itu.dk/people/ssrao/icalp03-a.pdf .

Opcja 2: Użyj rozkładu w pierwszym cyklu do zwięzłego przechowywania perm i wykorzystaj tę dodatkową przestrzeń, aby oszukać http://oeis.org/A186202

Opcja 3: Śledź największy indeks każdego zmanipulowanego cyklu. Dla każdej iteracji użyj największego niewidocznego indeksu, aby przenieść wszystko w jego cyklu o jeden. Jeśli trafi w widoczny indeks, cofnij całą pracę, ponieważ cykl został już zmanipulowany. , przestrzeń .$O(n^2)$$O(\#\text{cycles} * \log n)$

Opcja 4: Śledź największy indeks każdego zmanipulowanego cyklu, ale rób to tylko w partiach o różnych długościach cyklu. Dla każdej iteracji użyj największego niewidocznego indeksu, aby przenieść wszystko w jego cyklu o jeden. Jeśli trafi do widocznego indeksu, cofnij wszystko, co działa, ponieważ cykl został już zmanipulowany. czas, spacja.$O(n^2 * \text{distinct}\_\text{cycle}\_\text{lengths})$$O((\#\text{cycles}\_\text{with}\_\text{same}\_\text{size}) * \log n)$

Opcja 5: Z tego samego papieru Munro co opcja 0, dla obróć cykl jeżeli jest największym indeksem w tym cyklu. i przestrzeń .$i = 1 .. n$$p(i)$$i$$O(n^2)$$O(\log n)$

Jeśli używasz reprezentacji cyklu permutacji, potrzebujesz 1 dodatkowego elementu tablicy do przechowywania elementu, który jest obecnie permutowany, i możesz przechodzić cykle w gorszych operacjach O (N).

Każdą permutację N elementów można przekonwertować na dowolną inną permutację przy użyciu N-1 lub mniejszej liczby wymian. Najgorszy przypadek dla tej metody może wymagać wywołań O (n ^ 2) do twojej wyroczni, F (). Zacznij od najniższej pozycji. Niech x będzie pozycją, którą obecnie zamieniamy.

Jeśli F (x)> = x, zamień pozycje x i F (x). W przeciwnym razie musimy dowiedzieć się, gdzie pozycja, która była w pozycji F (x), znajduje się obecnie na liście. Możemy to zrobić z następującą iteracją. Niech y = F (x). Rób, aż y> = x: y = F (y): End Do. Teraz wymień pozycje xiy.

Ta metoda wykorzystuje odwrotność F i wymaga n bitów pamięci. Jeśli x jest pozycją elementu w oryginalnej tablicy, niech G (x) będzie pozycją elementu w posortowanej tablicy. Niech B będzie tablicą n-bitową. Ustaw wszystkie n bitów B na 0.

DLA x = 1 do n-1: JEŻELI B (x) == 0 NASTĘPNIE: y = G (x): ZRÓB DO X == y: Zamień pozycje x i y: B (y) = 1: y = G ( y): PĘTLA: KONIEC: NASTĘPNY X

Ta metoda polega na zamianie przedmiotu znajdującego się obecnie w pozycji x na pozycję końcową przedmiotu. Wewnętrzna pętla kończy się, gdy właściwy przedmiot zostanie zamieniony na pozycję x. Ponieważ każda zamiana przesuwa co najmniej jeden przedmiot do ostatecznej pozycji przedmiotu, wewnętrzna pętla Do nie może wycinać więcej niż n-1 razy podczas przebiegu. Myślę, że ta metoda to O (n) czas i przestrzeń.