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

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

Answer 2

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