Recursion - Java Concepts - page 809

6 public class PermutationGeneratorDemo
7 {
8 public static void main(String[] args)
9 {
10 PermutationGenerator generator
11 = new
PermutationGenerator( ÐeatÑ );
12 ArrayList<String> permutations =
generator.getPermutations();
13 for (String s : permutations)
14 {
15 System.out.println(s);
16 }
17 }
18 }

592
593

Output

eat
eta
aet
ate
tea
tae

Now we need a way to generate the permutations recursively. Consider the string
"eat" . Let's simplify the problem. First, we'll generate all permutations that start
with the letter ÓeÓ , then those that start with ÓaÓ , and finally those that start with Ó
tÓ . How do we generate the permutations that start with ÓeÓ ? We need to know the
permutations of the substring ÐatÑ . But that's the same problemȌto generate all
permutationsȌwith a simpler input, namely the shorter string "at" . Thus, we can
use recursion. Generate the permutations of the substring "at" . They are

"at"
"ta"

For each permutation of that substring, prepend the letter ÓeÓ to get the permutations
of ÐeatÑ that start with ÓeÓ , namely

" e at"
" e ta"