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ę ?
zliczyć liczbę spójnych składowych w grafie dla permutacji.
-
- Użytkownik
- Posty: 59
- Rejestracja: 2 gru 2014, o 18:25
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 17 razy
zliczyć liczbę spójnych składowych w grafie dla permutacji.
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.
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
zliczyć liczbę spójnych składowych w grafie dla permutacji.
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)
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)