Lets take a simple word like ‘cat’. How many permutations? Well, the answer is 6, or 3!. Why is that? Well, for the first character in the string, we have three choices. Once we have made a choice, we have two characters left, then one, so 3x2x1 = 3!.

To make these permutations, in a similar vein to how we calculate the number of permutations, we can start off with a base case and build up from there:

c -> ac, ca

ac -> tac, atc, act

ca -> tca, cta, cat

This lends itself conveniently to a recursive algorithm. We start with our base case, copy it, add an element to each copy at each potential index, and feed the new string back into the algorithm until we have used all potential characters. Therefore we track the current character we are on (and reset for each copy).