Recursion - Java Concepts - page 810

Now let's turn our attention to the permutations of "eat" that start with ÓaÓ . We
need to produce the permutations of the remaining letters, "et" . They are:

"et"
"te"

We add the letter ÓaÓ to the front of the strings and obtain

" a et"
" a te"

We generate the permutations that start with ÓtÓ in the same way.

That's the idea. The implementation is fairly straightforward. In the
get-Per mutations method, we loop through all positions in the word to be
permuted . For each of them, we compute the shorter word that is obtained by
removing the i th letter:

593
594

String shorterWord = word.substring(0, i) +
word.substring(i + 1);

We construct a permutation generator to get the permutations of the shorter word, and
ask it to give us all permutations of the shorter word.

PermutationGenerator shorterPermutationGenerator
= new PermutationGenerator(shorterWord);
ArrayList<String> shorterWordPermutations
= shorterPermutationGenerator.getPermutations();

Finally, we add the removed letter to the front of all permutations of the shorter word.

for (String s : shorterWordPermutations)
{
result.add(word.charAt(i) + s);
}

As always, we have to provide a special case for the simplest strings. The simplest
possible string is the empty string, which has a single permutationȌitself.

Here is the complete PermutationGenerator class.