[elektro-etc] String betuinek osszekeverese, de visszaallithatoan

[Karoly Kovacs]

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 kuldtel.

Karoly

-------- Original Message --------

>> Olyan algoritmus kellene nekem, amelyik egy szoveg betuit oszekeveri
>> (idaig oke, ilyet konnyu irni), de ugy, hogy visszaallithato legyen!
>>
>>
> 2 lehetőség:
>
> Innen indulnék:
> http://en.wikipedia.org/wiki/Permutation#Numbering_permutations
> esetleg
> http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
>
> A lényeg, hogy egy adott ismétlés nélküli permutációt kiválasztasz az n
> hosszúak közül, majd kikeresed vagy előállítod az inverzét. (egy permutáció
> valahogy megkeveri a füzér betűit)
> ---
> De ha egyszerűbben akarod, fogsz n-hez egy relatív prímet, lehetőleg
> nagyot. A füzér nulladik betűjét elrakod, lesz egy mutatód, ami először 0.
> n-szer végigmenve a számláló következő értékénél levő betűt a mostani érték
> helyére rakod. Következő érték pedig mostani + relatív prím modulo n.
> Utolsó helyre berakod az elrakott betűt.
>
> Utána elég elrakni a mutató utolsó értékét. Innen ugyanezt modulo n
> kivonásokkal megcsinálva visszaáll az eredeti állapot. Kevesebb lehetőség,
> mint permutációkkal, de egyszerű, teta(n) idejű algoritmus.
>
> szia: Balázs
>