[elektro-etc] String betuinek osszekeverese, de visszaallithatoan

[Balázs Bámer]

> 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