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

public class NumberPermutationIterator
{
private int[] a;
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--; }
}
}

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.4 without recursion.

Data from Exercise P13.4

Change the permutations method 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())
{

}
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.