Zagadka jest taka, że mając permutacje a
mamy znaleźć w czasie liniowym permutację odwrotną a^(-1)
z absolutnie stałym zużyciem pamięci, tj. w O(1)
pamięci nie korzystając nawet z tablicy, którą mamy na wejściu, możemy do niej wpisywać tylko wynik końcowy, nie cząstkowy. Można to sobie wyobrazić tak, że mamy tablice [0..n]
niepowtarzających się wartości [0..n]
i mamy zamienić indeksy tablicy z jej wartościami. Jakieś pomysły?
Może jakiś przykład?
O to ci chodzi: http://www.w3schools.com/php/func_array_flip.asp
@_13th_Dragon dokładnie o to chodzi
Jak "nie korzystając z tablicy którą mamy na wejściu"? Jakoś ją trzeba przeczytać tak czy inaczej.
Tak czy inaczej, skoro masz tablicę permutacji np.
3 2 5 1 4
(czyli 1szy element idzie na 3 miejsce, 2gi na 2gie, 3ci na 5te, etc), to odwrotna permutacja to:
4 2 1 5 3
Czyli w trzecie miejsce zapisujemy 1, drugie zapisujemy 2, piąte zapisujemy 3, itd.
Jesli zapisujesz do innej tablicy niż wejściowa:
def reverse(perm):
out = [0] * len(perm)
for i in range(len(perm)):
out[perm[i]] = i
return out
Ale nie możesz czegoś takiego zrobić (bo stała pamięć) tylko musisz pisać do wejściowej tablicy od razu wynik, więc możesz iść po kolei każdym cyklem z permutacji (tutaj tylko bardzo pseudokod bo nie chce mi się precyzyjnie pisać :P)
def reverse(perm):
for i in range(len(perm)):
if cycle_from_free(i):
invert_cycle_from(i)
return perm
Co to za magiczne funkcje:
Cycle_from_free(n) (przepraszam za nic nie mówiącą nazwę) sprawdza czy cykl zaczynający się w n
ma n
najbardziej z lewej strony (tzn. jest pierwszym indeksem cyklu).
Np. jesli permutacja rozłada sie na cykle (1, 3, 5) oraz (2, 4), to cycle_from_free zwróci true dla 1 (początek pierwszego cyklu) i 2 (początek drugiego cyklu), a false dla pozostałych indeksów.
Jedynym celem tej funkcji jest to, żeby każdy cykl został przetworzony tylko raz.
Natomiast invert_cycle_from odwraca cykl zaczynający się w i
. Można to bardzo łatwo zrobić liniowo, więc nie będę już rozpisywał więcej.
Złożoność czasowa algorytmu niestety O(n^2), bo cycle_from_free ma pesymistycznie liniowy koszt (gdyby się dało "oznaczać" pola w tablicy można by to załatwić w czasie O(n) - ale nie można).
Jak wrócę z pracy to spróbuję znaleźc coś szybszego.
Dla każdego elementu i
- Sprawdzamy gdzie ma przejść element potem kolejny i kolejny do pełnej pętli.
- Jeżeli pętla wyskoczyła powyżej
i
przechodzimy na kolejny element jeżeli nie to wymieniamy wzdłuż pętli, zapamiętując tylko jedną wartość.
koniec.