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 in-between them. From here, we can apply the same algorithm many times - for the four-letter 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.