Problem I
Knuth’s Permutation
Input: standard input
Output: standard output
There are some permutation generation techniques in 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 A2 … An-1, A1 n A2 … An-1, …., A1 A2 …n An-1, A1 A2, … An-1 n
For example, from the permutation 231 inserting 4 in all possible places we get 4231 2431 2341 2314
Following this rule you have to generate all the permutation for a given set of characters. All the given characters will be different and there number will be less than 10 and they all will be alpha numerals. This process is recursive and you will have to start 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 should exactly mach the sample output for the sample input.
Input
The input contains several lines of input. Each line will be a sequence of characters. There will be less than ten alphanumerals in each line. The input will be terminated by End of File.
Output
For each line of input generate the permutation of those characters. The input ordering is very important for the output. That is the permutation sequence for abc and bca will not be the same. Seperate each set of permutation output with a blank line.
Sample Input:
Sample Output: