Permutation algorithm without recursion? Java

Question

I would like to get all combination of a number without any repetition. Like 0.1.2, 0.2.1, 1.2.0, 1.0.2, 2.0.1, 2.1.0. I tried to find an easy scheme, but couldn't. I drew a graph/tree for it and this screams to use recursion. But I would like to do this without recursion, if this is possible.

Can anyone please help me to do that?

Answer 1

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