In this exercise, you will change the PermutationGenerator of Section 13.4 (which computed all permutations at once) to a PermutationIterator (which computes them one at a time.)

public class PermutationIterator

{

public PermutationIterator(String s) { . . . }

public String nextPermutation() { . . . }

public boolean hasMorePermutations() { . . . }

}

Here is how you would print out all permutations of the string "eat":

PermutationIterator iter = new PermutationIterator("eat");

while (iter.hasMorePermutations())

{

System.out.println(iter.nextPermutation());

}

Now we need a way to iterate through the permutations recursively. Consider the string "eat". As before, 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"? Make another PermutationIterator object (called tailIterator) that iterates through the permutations of the substring "at". In the nextPermutation method, simply ask tailIterator what its next permutation is, and then add the "e" at the front. However, there is one special case. When the tail generator runs out of permutations, all permutations that start with the current letter have been enumerated. Then

• Increment the current position.

• Compute the tail string that contains all letters except for the current one.

• Make a new permutation iterator for the tail string. You are done when the current position has reached the end of the string.