Programming contests

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

November 2, 2020 12:00 AM – November 8, 2020 11:59 PM

Knuth’s Permutation

There are some permutation generation techniques in Donald E. Knuth’s book The Art of Computer Programming – Volume 1. One of the processes is as follows:

For each permutation A1, A2, …, An-1, form n others by inserting a character n in all possible places, obtaining

n A1 A2An-1
A1 n A2An-1

A1 A2n An-1
A1 A2An-1 n

For example, from the permutation 231, inserting 4 in all possible places, we get the following new permutations: 4231, 2431, 2341, 2314.

Following this rule, you have to generate all permutations for a given set of characters. All the given characters will be different and their number will be less than 10 and they all will be alphanumeric characters. This process is recursive, and you will have to start the recursive call with the first character and keep inserting the other characters in order. The sample input and output will make this clear. Your output for the sample input should exactly match the sample output.

Input Specification

The input contains several lines. Each line will be a sequence of characters.There will be less than ten alphanumeric characters in each line. The input will be terminated by EOF.

Output Specification

For each line of input, generate all permutations of those characters. The ordering of the input characters is very important for the output. That is, the permutation sequences for abc and bca will not be the same. Seperate each set of permutations with a blank line.

Sample Input

  1. abc
  2. bca
  3. dcba
download as text file

Output for Sample Input

  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
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019