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 A₁, A₂, …, A_n-1, form n others by inserting a character n in all possible places, obtaining

n A₁ A₂ … A_n-1
A₁ n A₂ … A_n-1
⋮
A₁ A₂ … n A_n-1
A₁ A₂ … A_n-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
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

download as text file