The following class generates all permutations of the numbers 0, 1, 2, . . ., n − 1, without using recursion.

public class NumberPermutationIterator
{
   public NumberPermutationIterator(int n)
   {
      a = new int[n];
      done = false;
      for (int i = 0; i < n; i++) a[i] = i;
   }

   public int[] nextPermutation()
   {
      if (a.length <= 1) { return a; }
   
      for (int i = a.length - 1; i > 0; i--)
      {
         if (a[i - 1] < a[i])
         {
            int j = a.length - 1;
            while (a[i - 1] > a[j]) j--;
            swap(i - 1, j);
            reverse(i, a.length - 1);
            return a;
         }
      }
      return a;
   }

   public boolean hasMorePermutations()
   {
      if (a.length <= 1) { return false; }
      for (int i = a.length - 1; i > 0; i--)
      {
         if (a[i - 1] < a[i]) { return true; }
      }
      return false;
   }

   public void swap(int i, int j)
   {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
   }

   public void reverse(int i, int j)
   {
      while (i < j) { swap(i, j); i++; j--; }
   }
   private int[] a;
}

The algorithm uses the fact that the set to be permuted consists of distinct numbers. Thus, you cannot use the same algorithm to compute the permutations of the characters in a string. You can, however, use this class to get all permutations of the character positions and then compute a string whose ith character is word.charAt(a[i]). Use this approach to reimplement the PermutationIterator of Exercise P13.11 without recursion.

Complete the following files:

PermutationIterator.java

PermutationIteratorTester2.java

PermutationIteratorTester3.java

Use the following files:

NumberPermutationIterator.java

public class NumberPermutationIterator
{
   private int[] a;

   public NumberPermutationIterator(int n)
   {
      a = new int[n];
      for (int i = 0; i < n; i++) { a[i] = i; }
   }

   public int[] nextPermutation()
   {
      if (a.length <= 1) { return a; }
      for (int i = a.length - 1; i > 0; i--)
      {
         if (a[i - 1] < a[i])
         {
            int j = a.length - 1;
            while (a[i - 1] > a[j]) j--;
            swap(i - 1, j);
            reverse(i, a.length - 1);
            return a;
         }
      }
      return a;
   }
   
   public boolean hasMorePermutations()
   {
      if (a.length <= 1) return false;
      for (int i = a.length - 1; i > 0; i--)
      {
         if (a[i - 1] < a[i]) return true;
      }
      return false;
   }
   
   public void swap(int i, int j)
   {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
   }
   
   public void reverse(int i, int j)
   {
      while (i < j) { swap(i, j); i++; j--; }
   }
}

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");
   }
}