Knuth-féle permutáció

Donald E. Knuth A számítógép-programozás művészete című könyvének 1. kötetében található néhány módszer egy elemsorozat összes permutációjának legenerálására. Az egyik ilyen algoritmus a következő:

Minden A₁, A₂, …, A_n-1 permutáció esetén képezzünk n újabb permutációt úgy, hogy szúrjuk be az n karaktert minden lehetséges pozícióba:

n A₁ A₂ … A_n-1
A₁ n A₂ … A_n-1
⋮
A₁ A₂ … n A_n-1
A₁ A₂ … A_n-1 n

A 231 permutációból a 4 minden lehetséges pozícióba történő beszúrása után például az alábbi új permutációkat kapjuk: 4231, 2431, 2341, 2314.

A fenti módszert alkalmazva le kell generálnod megadott karakterek összes lehetséges permutációját. Minden karakter különböző lesz, számuk kisebb lesz, mint 10, és mindegyikük alfanumerikus karakter lesz. Ez egy rekurzív folyamat; a rekurzív hívásokat az első karakterrel kell kezdened, sorban beszúrva a többi karaktert, ahogyan a példa input és output mutatja. A programodnak a példa inputra pontosan a példa outputot kell eredményeznie.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz, mindegyiket külön sorban. Minden sor egy karaktersorozatból áll, amelyben 10-nél kevesebb alfanumerikus karakter szerepel. A bemenetet EOF zárja.

A kimenet specifikációja

Minden tesztesetre a megadott karakterek összes lehetséges permutációját kell a kimenetre írni. A bemeneten megadott karakterek sorrendje nagyon fontos a kimenet szempontjából, tehát az abc és a bca bemenetre kapott permutációsorozat nem ugyanaz. Az egyes tesztesetekhez tartozó permutációsorozatokat egy-egy üres sorral kell elválasztani.

Példa bemenet

1. abc
2. bca
3. dcba

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. cba
2. bca
3. bac
4. cab
5. acb
6. abc
8. acb
9. cab
10. cba
11. abc
12. bac
13. bca
15. abcd
16. bacd
17. bcad
18. bcda
19. acbd
20. cabd
21. cbad
22. cbda
23. acdb
24. cadb
25. cdab
26. cdba
27. abdc
28. badc
29. bdac
30. bdca
31. adbc
32. dabc
33. dbac
34. dbca
35. adcb
36. dacb
37. dcab
38. dcba

letöltés szöveges állományként