Złożoność zastosowania permutacji w miejscu

27

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)$

ds.algorithms co.combinatorics permutations

— jkff
źródło

Łatwa obserwacja: jeśli nie tylko tablica elementów, ale także tablica zawierająca funkcję f jest zapisywalna, to łatwo jest wykonać zadanie w czasie O (n) za pomocą rejestrów całkowitych O (1) (każda o długości O ( log n) bitów) i dodatkowe miejsce dla jednego elementu, po prostu wykonując każdy cykl. Ale to nie działa, jeśli funkcja f jest podana w pamięci tylko do odczytu (lub f jest podana tylko jako wyrocznia), co moim zdaniem jest założeniem w tym pytaniu.

— Tsuyoshi Ito

23

Fich i in. 1995 : Czas , przestrzeń . Omówiono także niektóre przypadki szczególne.

O (n \log n)

$O(n \log n)$

O (\log n)

$O(\log n)$

— Jukka Suomela

Tak, zakładam, że mamy f jako wyrocznię.

— jkff

3

@JukkaSuomela, powinieneś zrobić z tego odpowiedź. Biorąc również pod uwagę, że jest dowolną permutacją, prosty argument entropijny daje przestrzeń i / lub czas, więc byłbym zaskoczony, gdybyś mógł zrobić coś lepszego niż w czasie i przestrzeni .

f

$f$

O (n \log n)

$O( n \log n)$

O (n \log n)

$O(n \log n)$

— user834

4

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)$

— Chad Brewbaker
źródło

metody kompresji mogą ogólnie nie oszczędzać miejsca: najgorszym miejscem do przechowywania permutacji jest . 3, 4 i 5 wydają się ogólnie tak złe, jak albo rozwiązanie OP już wie, albo rozwiązanie Ficha, Munro i Poblete. I to rozwiązanie zostało już wskazane przez @Jukka

n \log n

$n\log n$

— Sasho Nikolov

# 5 zajmuje mniej miejsca niż # 0 przez współczynnik log (n).

— Chad Brewbaker

1

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).

— Phil
źródło

2

jkff już powiedział, że zna algorytm śledzenia cyklu, więc wyraźnie chce, aby samą permutację traktować jako (blisko) czarną skrzynkę. Jak wskazuje w pytaniu, przejście z (prawie) czarnej skrzynki do reprezentacji cyklu może zająć czas O (n ^ 2).

— Joshua Grochow

Czarna skrzynka p (i) jest w porządku. Kręcisz się po cyklu, dopóki nie wrócisz do mnie. Problem polega na tym, że złożoność Kołomogorowa polega na przechowywaniu listy elementów, które zostały zaktualizowane, więc nie należy ich cyklicznie powtarzać. Munro ma na to granice. itu.dk/people/ssrao/icalp03-a.pdf

— Chad Brewbaker

-2

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.

— Russell Easterly
źródło

3

OP już powiedział, że wie, jak to zrobić w czasie .

O (n^{2})

$O(n^2)$

— Jukka Suomela,

Przepraszam. Jestem nowy w tej grupie. Podoba mi się ta metoda ze względu na jej prostotę. Czasami prostotę znajduję szybciej niż wydajność. Znam inną metodę, która wymaga kroków O (n), ale przestrzeń O (nlogn).

— Russell Wielkanocny

1

Russell, nawet przydzielając i zerując przestrzeń O (n log n) jest już O (n log n), miałeś na myśli w innym kierunku?

— jkff

Tak naprawdę nie masz przydzielonej i zerowej przestrzeni. Podstawową ideą jest to, że gdy F (x)> x musimy pamiętać, gdzie umieszczamy element w pozycji x. W przypadku naprawdę dużego n użyłbym bazy danych i po prostu zapisywałbym, gdzie element x zostanie przeniesiony. Rekord może zostać usunięty, gdy x dotrze do swojej ostatecznej lokalizacji.

— Russell Wielkanocny

1

Ale dlaczego mówisz, że wymaga miejsca O (n log n)?

— jkff

-2

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ń.

— Russell Easterly
źródło

2

Czy spojrzałeś na gazetę? Dwa wymienione tutaj algorytmy to dwa „oczywiste”. Papier ma mniej oczywiste z różnymi kompromisami czasoprzestrzennymi, w szczególności znacznie mniejszą przestrzenią.

— Yuval Filmus