Java Reference
In-Depth Information
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.