Znajdowanie wszystkich cykli

Mam skończony zestaw $S$, funkcja $f:S\to S$oraz całkowite zamówienie $<$ na $S$. Chcę znaleźć liczbę różnych cykli$S$.

Dla danego elementu $s\in S$ Mogę użyć algorytmu Floyda (lub Brenta itp.), Aby znaleźć długość cyklu, w którym powtarzały się aplikacje $f$ wysyła $s$do; przy odrobinie wysiłku mogę zidentyfikować ten cykl (np. po jego$<$-minimal element). Złą metodą rozwiązania problemu byłoby powtórzenie tego każdego elementu, posortowanie powstałych minimalnych elementów odrzucających duplikaty i zwrócenie liczby. Ale potencjalnie wymaga to wielu przejść przez te same elementy i dużych wymagań przestrzennych.

Jakie metody mają lepszą wydajność w czasie i przestrzeni? Nie jestem nawet pewien, jaki jest najlepszy sposób zmierzenia potrzebnej przestrzeni - jeśli$f$ jest funkcją tożsamości, to zastosuje ją dowolna metoda przechowująca wszystkie cykle $\Omega(n)$ przestrzeń.

Jeśli wszystko, co chcesz zrobić, to policzyć liczbę cykli, możesz to zrobić za pomocą 2 | S | bitów (plus zmiana) przestrzeni. Wydaje się mało prawdopodobne, że będziesz w stanie zrobić znacznie lepiej, chyba że S lub f mają jakieś szczególnie wygodne właściwości.

Zacznij od tablicy A przechowującej liczby całkowite {0,1,2} - jeden na element S - zainicjowany na zero; będziemy oznaczać je jako (unexplored), (partially explored), i (fully explored). Zainicjuj licznik cykli do zera. Dla każdego elementu s  ∈  S w kolejności wykonaj następujące czynności:

1. Jeśli A [ s ] =  (fully explored), przejdź do kroku 6.
2. Ustaw A [ s ] ←  (partially explored)i ustaw iterator j  ←  f (s) .
3. Gdy A [ j ] =  (unexplored), ustaw A [ j ] ←  (partially explored)i ustaw j  ←  f (j) .
4. Jeśli A [ j ] =  (partially explored), zamknęliśmy nowy cykl; przyrost c o 1. (Jeśli chcesz prowadzić rejestr jakiegoś przedstawiciela tego cyklu, bieżąca wartość j zrobi jako arbitralny wybór; oczywiście niekoniecznie będzie to minimalny element w cyklu zgodnie z twoim preferowanym kolejność <.) W przeciwnym razie mamy A [ j ] =  (fully explored), co oznacza, że ​​odkryliśmy wcześniej zbadaną orbitę, która kończy się już zliczonym cyklu; nie zwiększać c .
5. Aby wskazać, że orbita rozpoczynająca się od s została już w pełni zbadana, ustaw j  ←  s .
   Gdy A [ j ] =  (partially explored), ustaw A [ j ] ←  (fully explored)i ustaw j  ←  f (j) .
6. Przejść do następnego elementu, s  ∈  S .

Zatem każdy cykl między orbitami indukowanymi przez f będzie zliczony raz; a wszelkie elementy rejestrowane jako przedstawiciele będą elementami odrębnych cykli. Wymagania dotyczące pamięci wynoszą 2 | S | dla tablicy A, O (log | S |) dla liczby cykli i innych szans i zakończeń.

Każdy element s  ∈  S będzie odwiedzany co najmniej dwa razy: raz, gdy wartość A [ s ] zostanie zmieniona z (unexplored)na (partially explored), i raz dla zmiany na (fully explored). Łączna liczba ponownych odwiedzin węzłów po ich (fully explored)ograniczeniu jest ograniczona liczbą prób znalezienia nowych cykli, które tego nie robią, co najwyżej | S | - wynikające z głównego iteracji pętli wszystkich elementów S . Dlatego możemy oczekiwać, że ten proces będzie obejmował co najwyżej 3 | S | przejazdy węzłów, licząc wszystkie odwiedziny lub odwiedziny węzłów.

Jeśli chcesz śledzić reprezentatywne elementy cykli i naprawdę chciałbyś, aby były to elementy minimalne, możesz ograniczyć liczbę odwiedzin węzłów do 4 | S |, jeśli dodasz dodatkowe „okrążenie wokół cyklu” w kroku 4, aby znaleźć przedstawiciela, który jest mniejszy niż ten, w którym zamykasz pętlę. (Jeśli orbity pod f składały się tylko z cykli, można by uniknąć tej dodatkowej pracy, ale nie jest to prawdą w przypadku arbitralnych f .)

Jeśli masz bardzo mało cykli, oto algorytm, który zużyje mniej miejsca, ale jego zakończenie zajmuje znacznie więcej czasu.

[Edytuj.] W mojej poprzedniej analizie w czasie wykonywania pominięto kluczowy koszt ustalenia, czy odwiedzane przez nas węzły należą do tych, z których wcześniej pobrano próbki; ta odpowiedź została nieco poprawiona, aby to poprawić.

Znów iterację wszystkich elementów S . Jak badamy orbity z elementów s  ∈  S , to próbki z węzłów, które my odwiedziliśmy, aby być w stanie sprawdzić, czy możemy się z nimi ponownie. Prowadzimy również listę próbek „składników” - związków orbit, które kończą się we wspólnym cyklu (i dlatego są równoznaczne z cyklami) - które były wcześniej odwiedzane.

Zainicjować pustą listę składników complist. Każdy komponent jest reprezentowany przez zbiór próbek z tego komponentu; utrzymujemy również drzewo wyszukiwania, samplesktóre przechowuje wszystkie te elementy, które zostały wybrane jako próbki dla jakiegoś komponentu lub innego. Niech G będzie ciągiem liczb całkowitych do n , dla których członkostwo można skutecznie określić przez obliczenie jakiegoś predykatu logicznego; na przykład potęgi 2 lub idealne p ^th potęgi dla jakiejś liczby całkowitej p . Dla każdego s  ∈  S wykonaj następujące czynności:

1. Jeśli s jest samples, przejdź do kroku 5.
2. Zainicjuj pustą listę cursample, iterator j  ← f ( s ) i licznik t  ← 1.
3. Gdy j nie jest w samples:
   - Jeśli t  ∈  G , wstaw j do obu cursamplei samples.
   - Przyrost T i zestaw J  ←  f (j) .
4. Sprawdź, czy j jest włączonycursample . Jeśli nie, napotkaliśmy wcześniej zbadany komponent: sprawdzamy, do którego komponentu należy j , i wstawiamy wszystkie elementy cursampledo odpowiedniego elementu, complistaby go powiększyć. W przeciwnym razie ponownie napotkaliśmy element z bieżącej orbity, co oznacza, że ​​przemierzyliśmy cykl co najmniej raz, nie napotykając żadnych przedstawicieli wcześniej odkrytych cykli: wstawiamy cursample, jako zbiór próbek z nowo znalezionego komponentu, do complist.
5. Przejść do następnego elementu, s  ∈  S .

Dla n  = | S |, niech X (n) będzie funkcją monotoniczną zwiększającą opisującą oczekiwaną liczbę cykli ( np.  X (n) =  n ^1/3 ), i niech Y (n) = y (n)  log ( n ) ∈ Ω ( X (n)  log ( n )) jest monotoniczną funkcją zwiększającą, określającą cel wykorzystania pamięci ( np.  Y (n) =  n ^1/2 ). Wymagamy y (n)  ∈ Ω ( X (n) ), ponieważ zajmie co najmniej X (n)  log ( n ) miejsca do przechowywania jednej próbki z każdego komponentu.

• Im więcej elementów orbity próbkujemy, tym bardziej prawdopodobne jest, że szybko wybieramy próbkę w cyklu na końcu orbity, a tym samym szybko wykrywamy ten cykl. Z asymptotycznego punktu widzenia sensowne jest wówczas uzyskanie tylu próbek, na ile pozwalają nasze granice pamięci: równie dobrze możemy ustawić G, aby mieć oczekiwane elementy y (n) , które są mniejsze niż n .
  - Jeśli spodziewana jest maksymalna długość orbity w S, to L , możemy pozwolić, aby G była wielokrotnością całkowitą L  /  y (n) .
  - Jeśli nie ma oczekiwanej długości, możemy po prostu próbkować raz co n  / r  (n)elementy; jest to w każdym razie górna granica odstępów między próbkami.

• Jeśli szukając nowego komponentu, zaczniemy przemierzać elementy S, które wcześniej odwiedziliśmy (albo z nowego odkrytego komponentu, albo ze starego, którego cykl końcowy został już znaleziony), zajmie to najwyżej n  / r  ( n) iteracje napotkane wcześniej próbkowany element; jest to wtedy górna granica liczby razy, przy każdej próbie znalezienia nowego komponentu przemierzamy zbędne węzły. Ponieważ podejmujemy n takich prób, wówczas nadmiarowo odwiedzimy elementy S łącznie łącznie maksymalnie n ²  / r  (n) razy.

• Praca wymagana do przetestowania członkostwa samplesto O ( y (n)  log  y (n) ), którą powtarzamy przy każdej wizycie: skumulowany koszt tego sprawdzenia wynosi O ( n ²  log  y (n) ). Istnieje również koszt dodania próbek do ich odpowiednich kolekcji, które łącznie wynoszą O ( y (n)  log  y (n) ). Wreszcie, za każdym razem, gdy ponownie napotykamy wcześniej wykryty komponent, musimy poświęcić do X (n)  log *  y (n) czas, aby określić, który komponent został ponownie odkryty; ponieważ może się to zdarzyć nawet n razy, skumulowana praca jest ograniczona przez n X (n)  log  y (n) .

Zatem łączna praca wykonana w celu sprawdzenia, czy odwiedzane przez nas węzły znajdują się wśród próbek, dominuje w czasie wykonywania: kosztuje to O ( n ²  log  y (n) ). Następnie powinniśmy uczynić y (n) tak małym, jak to możliwe, to znaczy O ( X (n) ).

Zatem można wyliczyć liczbę cykli (która jest taka sama jak liczba składników kończących się tymi cyklami) w przestrzeni O ( X (n)  log ( n )), biorąc O ( n ²  log  X (n) ) czas to zrobić, gdzie X (n) jest oczekiwaną liczbą cykli.

Można uniknąć wielokrotnych przejść przez te same elementy, używając struktury danych zestawu unii . Jedno przejście przez każdy element$s$ połączenie zestawu zawierającego $s$ z zestawem zawierającym $f(s)$. To wciąż zużywa dużo pamięci.