Permutations 2 X87168

Some genome rearrangements change the order of the nucleotides in a nucleic acid sequence, resulting in a permutation of the nucleic acid sequence. For example, TATATA is a frequent rearrangement of TATAAT. An interesting problem is the generation of all the permutations of a genomic sequence of length $n$.

Write code for the permutations problem. The program must implement and use the PERMUTATIONS function in the pseudocode discussed in class, which is recursive and is not allowed to perform input/output operations. Make one submission with Python code and another submission with C++ code.

Input

The input is a string $s$ over the alphabet $\Sigma=\{A,C,G,T\}$.

Output

The output is a sorted list of all the permutations of $s$, without repetitions.

Hint

There are at most $n!$ permutations of a genomic sequence of length $n$.