[elektro-etc] String betuinek osszekeverese, de visszaallithatoan

[Balázs Bámer]

Szervusz Károly!

> Koszi Balazs, megneztem, de elso blikkre nagyon ugy tunik, hogy ez nem
reverzibilis. Szoval talalni kellene
> ra valami "megforditott" scramble megoldast is. Azert tovabb torom a
fejem rajta, mert alapvetoen jo a link, amit

Közben kitaláltam egy tetszőleges permutáció megfordításának algoritmusát
is. Tök egyszerű, jellemezze a permutációt egy P tömb. Indexek, elemek
0..n-1, az elem azt jelzi, hogy a füzérben a tömbelemnek megfelelő helyre
melyik karakter kerül.

Megfordítás Q tömbbe kerül. Q[i] = P-ben i indexe. Utána lehet nézni, a
permutációk adott felsorolását tekintve ez az eredeti permutáció
sorszámából számítható-e. Triviális algoritmus tetszőleges füzérméret setén
O(n^2), de érzésem szerint lejjebb is szorítható.

szia: Balázs