Permutation algorithm without recursion? Java
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?
Solution 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);
}
}
Solution 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).
Solution 3:
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.
Solution 4:
It is easy to write the recursive permutation, but it requires exporting the permutations from deeply nested loops. (That is an interesting exercise.) I needed a version that permuted strings for anagrams. I wrote a version that implements Iterable<String> so it can be used in foreach loops. It can easily be adapted to other types such as int[] or even a generic type <T[]> by changing the constructor and the type of attribute 'array'.
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* An implicit immutable collection of all permutations of a string with an
* iterator over the permutations.<p> implements Iterable<String>
* @see #StringPermutation(String)
*/
public class StringPermutation implements Iterable<String> {
// could implement Collection<String> but it's immutable, so most methods are essentially vacuous
protected final String string;
/**
* Creates an implicit Iterable collection of all permutations of a string
* @param string String to be permuted
* @see Iterable
* @see #iterator
*/
public StringPermutation(String string) {
this.string = string;
}
/**
* Constructs and sequentially returns the permutation values
*/
@Override
public Iterator<String> iterator() {
return new Iterator<String>() {
char[] array = string.toCharArray();
int length = string.length();
int[] index = (length == 0) ? null : new int[length];
@Override
public boolean hasNext() {
return index != null;
}
@Override
public String next() {
if (index == null) throw new NoSuchElementException();
for (int i = 1; i < length; ++i) {
char swap = array[i];
System.arraycopy(array, 0, array, 1, i);
array[0] = swap;
for (int j = 1 ; j < i; ++j) {
index[j] = 0;
}
if (++index[i] <= i) {
return new String(array);
}
index[i] = 0;
}
index = null;
return new String(array);
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}