Odwrócenie permutacji in place

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.