Matematyka.pl

Mamy permutację liczb \(\displaystyle{ 1...n}\). Konstruujemy graf wierzchołków \(\displaystyle{ 1...n}\) w ten sposób, że dwa wierzchołki są połączone (krawędź nieskierowana) wtw gdy są one w inwersji ze sobą.

Naszym zadaniem jest wymyślić algorytm, który dla danej permutacji policzy ile graf ma spójnych składowych:

Ja zaproponuję coś takiego: (proszę o sprawdzenie, ale także pokazanie alternatywnych rozwiązań).
To rozwiązanie działa w czasie \(\displaystyle{ O(n\log^*)}\)
Używamy Union find, na początku \(\displaystyle{ 1...n}\) to osobne zbiory.

1. Policzmy tablicę sufixową dla minimów. Tzn dla każdego sufixu znamy minimum.
2. Sprawdzamy jakie jest minimum na przedziale \(\displaystyle{ [1..n]}\). Okazuje się, że to \(\displaystyle{ p}\). Wówczas lecimy
od \(\displaystyle{ 1}\) do \(\displaystyle{ i-1}\) i wszystkie scalamy z \(\displaystyle{ p}\) - dostajemy jeden zbiór. Potem powtarzamy to samo, w konsekwencji jesteśmy w sytuacji takiej:



I teraz:
Bierzemy maximum - niebieska kropka - z grupki pierwszej. Porównujemy go z minimum grupki drugiej:
Jeśli niebieska kropka (max) jest większa niż czerwona (min) to mamy inwersję i scalamy (UNION) obie grupki. Jedną (mniejszą) z niebieskich kropek eliminujemy i kontynuujemy.

Jeśli niebieska kropka (max) jest mniejsza niż czerwona (min) to żaden element z pierwszej grupki nie jest w inwersji z żadną inną grupką. Dlatego zapominamy o pierwszej grupce. I postępujemy tak samo dalej.

Co teraz ? Teraz zliczamy ilość zbiorów.

Czy to jest ok ? Ma ktoś pomysł na szybszą implementację ?

Find union to overkill w tym przypadku, bo masz znaleźć tylko ilość składowych. Wyrzuć z twojego algorytmu operacje union oraz przerzuć szukanie maksimów i "scalanie składowych" (nie scalaj, tylko zliczaj je według twojego pomysłu z minimami i maksimami) do drugiej części kroku 2.

0. Powiedz coś więcej proszę.
1. Ogólna idea ok ?
2. To działa ?-- 28 wrz 2015, o 10:22 --Ok, przedstawię coś takiego:
1. Policzmy tablicę sufixową dla minimów. Tzn. dla każdego sufixu znamy minimum.
2. Sprawdzamy jakie jest minimum na przedziale . Okazuje się, że to . Wówczas lecimy 1…i i wszystkim elementom nadajemy id = 1. Potem powtarzamy to samo (nadając coraz to większe id), w konsekwencji jesteśmy w sytuacji takiej: Zauważmy, że minima są posortowane rosnąco od lewej do prawej. Stąd jeśli maximum (kropka niebieska) ze zbioru o id = k jest mniejsze niż minimum (czerwona kropka) zbioru k+1, to tym bardziej jest mniejsze niż minima zbiorów o większych id, a więc zbiór k-ty nie może zostać z niczym scalony scalony. Wtedy przechodzimy do kolejnej grupki.
Jeśli jednak niebieska kropka zbioru k-tego jest większa niż czerwona kropka k+1-go to wszystkim elementom zbioru k+1-go nadajemy id = k – scaliliśmy dwa zbiory. Następnie eliminujemy jednego z kandydatów na maximum i kontynuujemy algorytm.

(znalezienie maximum dla każdej grupki może zostać zrealizowane w czasie liniowym)