Programozó versenyek

INBPM9931 Magas szintű programozási nyelvek 3, gyakorló feladatsor

2020. november 2. 0:00 – 2020. november 8. 23:59

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 A1, A2, …, An-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 A1 A2An-1
A1 n A2An-1

A1 A2n An-1
A1 A2An-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
  7. acb
  8. cab
  9. cba
  10. abc
  11. bac
  12. bca
  13. abcd
  14. bacd
  15. bcad
  16. bcda
  17. acbd
  18. cabd
  19. cbad
  20. cbda
  21. acdb
  22. cadb
  23. cdab
  24. cdba
  25. abdc
  26. badc
  27. bdac
  28. bdca
  29. adbc
  30. dabc
  31. dbac
  32. dbca
  33. adcb
  34. dacb
  35. dcab
  36. dcba
letöltés szöveges állományként
Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.