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

You are done when the current position has reached the end of the string.

Complete the following files:

PermutationIterator.java

PermutationIteratorTester2.java

PermutationIteratorTester3.java

Use the following file:

PermutationIteratorTester.java

import java.util.ArrayList;

/**
   This program tests the permutation generator.
*/
public class PermutationIteratorTester
{
   public static void main(String[] args)
   {
      PermutationIterator iter = new PermutationIterator("eat");
      System.out.println(iter.nextPermutation());
      System.out.println("Expected: eat");
      System.out.println(iter.nextPermutation());
      System.out.println("Expected: eta");
      System.out.println(iter.nextPermutation());
      System.out.println("Expected: aet");
      System.out.println(iter.nextPermutation());
      System.out.println("Expected: ate");
      System.out.println(iter.nextPermutation());
      System.out.println("Expected: tea");
      System.out.println(iter.nextPermutation());
      System.out.println("Expected: tae");
      System.out.println(iter.hasMorePermutations());
      System.out.println("Expected: false");
   }
}