Permutation algorithm without recursion? Java

You should use the fact that when you want all permutations of N numbers there are N! possibilities. Therefore each number x from 1..N! encodes such a permutation. Here is a sample that iteratively prints out all permutations of a sting.

private static void printPermutationsIterative(String string){        int [] factorials = new int[string.length()+1];        factorials[0] = 1;        for (int i = 1; i<=string.length();i++) {            factorials[i] = factorials[i-1] * i;        }        for (int i = 0; i < factorials[string.length()]; i++) {            String onePermutation="";            String temp = string;            int positionCode = i;            for (int position = string.length(); position > 0 ;position--){                int selected = positionCode / factorials[position-1];                onePermutation += temp.charAt(selected);                positionCode = positionCode % factorials[position-1];                temp = temp.substring(0,selected) + temp.substring(selected+1);            }            System.out.println(onePermutation);        }    }

Here is a generic permutation enumerator I wrote a year ago. It can also produce "sub-permutations":

public class PermUtil <T> { private T[] arr; private int[] permSwappings; public PermUtil(T[] arr) {  this(arr,arr.length); } public PermUtil(T[] arr, int permSize) {  this.arr = arr.clone();  this.permSwappings = new int[permSize];  for(int i = 0;i < permSwappings.length;i++)   permSwappings[i] = i; } public T[] next() {  if (arr == null)   return null;  T[] res = Arrays.copyOf(arr, permSwappings.length);  //Prepare next  int i = permSwappings.length-1;  while (i >= 0 && permSwappings[i] == arr.length - 1) {   swap(i, permSwappings[i]); //Undo the swap represented by permSwappings[i]   permSwappings[i] = i;   i--;  }  if (i < 0)   arr = null;  else {      int prev = permSwappings[i];   swap(i, prev);   int next = prev + 1;   permSwappings[i] = next;   swap(i, next);  }  return res; } private void swap(int i, int j) {  T tmp = arr[i];  arr[i] = arr[j];  arr[j] = tmp; }}

The idea behind my algorithm is that any permutation can be expressed as a unique sequence of swap commands. For example, for <A,B,C>, the swap sequence 012 leaves all items in place, while 122 starts by swapping index 0 with index 1, then swaps 1 with 2, and then swaps 2 with 2 (i.e. leaves it in place). This results in the permutation BCA.

This representation is isomorphic to the permutation representation (i.e. one to one relationship), and it is very easy to "increment" it when traversing the permutations space. For 4 items, it starts from 0123 (ABCD) and ends with 3333(DABC).

In general, any recursive algorithm can always be reduced to an iterative one through the use of stack or queue data structures.

For this particular problem, it might be more instructive to look at the C++ STL algorithm std::next_permutation. According to Thomas Guest at wordaligned.org, the basic implementation looks like this:

template<typename Iter>bool next_permutation(Iter first, Iter last){    if (first == last)        return false;    Iter i = first;    ++i;    if (i == last)        return false;    i = last;    --i;    for(;;)    {        Iter ii = i;        --i;        if (*i < *ii)        {            Iter j = last;            while (!(*i < *--j))            {}            std::iter_swap(i, j);            std::reverse(ii, last);            return true;        }        if (i == first)        {            std::reverse(first, last);            return false;        }    }}

Note that it does not use recursion and is relatively straightforward to translate to another C-like language like Java. You may want to read up on std::iter_swap, std::reverse, and bidirectional iterators (what Iter represents in this code) as well.