18.3 Listing all permutations of a string
Sometimes, we have a string (e.g. "MATHS"), of which we’d like to list out all the possible permutations. To list these, we have to do this systematically. A nice way to do this is using Heap’s algorithm. To generate all the permutations of a string, we first pick one letter. When we generate all the permutations of this string, we will have different strings, each of which has that letter at a different position. For example, in the case of "MATHS", we will have all the following (where \say_ means we don’t know what letter will be at that position.)

•\say
M____

•\say
_M___

•\say
__M__

•\say
___M_

•\say
____M
The key idea of Heap’s algorithm is that in each of these cases, the valid choices for the four unknown items (\say_) are any of the permutations of the four letters in question. This means that we’ve found a way to write the permutations of five letters (which we don’t know) in terms of the permutations of four letters arranged with a known letter inbetween them. From here, we can apply the same algorithm many times  for the fourletter permutation we can reduce it to a three letter permutation, and so on until we have only one letter left. In this case, there is only one possible permutation.
There are too many possibilities here to list out all the permutations, but for the first one (\sayM____), the process would go something like this:

•\say
MA___

•\say
M_A__

•\say
M__A_

•\say
M___A
If we then pick the first one here (the process for the rest is the same) we have

•\say
MAT__

•\say
MA_T_

•\say
MA__T
proceeding with the first one again

•\say
MATH_

•\say
MAT_H
and then finally

•\say
MATHS
There are a lot more possibilities than that, but I’ve only listed out some of them; to obtain the full list, just continue the process.