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:

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