If you don't want to store all permutations, but only to have possibility to iterate over all permutations, then you can expand the recursion. Consider the following class which implements Iterator<int[]>
interface:
public class IntPermutationsGenerator implements Iterator<int[]> {
final int[] permutation;
private boolean onFirst = true;
private final int size;
public IntPermutationsGenerator(int dimension) {
permutation = new int[dimension];
for (int i = 0; i < dimension; ++i)
permutation[i] = i;
this.size = dimension;
}
@Override
public boolean hasNext() {
return !isLast() || onFirst;
}
private boolean isLast() {
for (int i = 0; i < size; i++)
if (permutation[i] != size - 1 - i)
return false;
return true;
}
@Override
public int[] next() {
if (onFirst) {
onFirst = false;
return permutation;
}
final int end = size - 1;
int p = end, low, high, med, s;
while ((p > 0) && (permutation[p] < permutation[p - 1]))
p--;
if (p > 0) //if p==0 then it's the last one
{
s = permutation[p - 1];
if (permutation[end] > s)
low = end;
else {
high = end;
low = p;
while (high > low + 1) {
med = (high + low) >> 1;
if (permutation[med] < s)
high = med;
else
low = med;
}
}
permutation[p - 1] = permutation[low];
permutation[low] = s;
}
high = end;
while (high > p) {
med = permutation[high];
permutation[high] = permutation[p];
permutation[p] = med;
p++;
high--;
}
return permutation;
}
@Override
public void remove() {
throw new UnsupportedOperationException("Not supported yet.");
}
}
This class allows to iterate over all permutations without storing them:
public void main(String[] args) throws Exception {
IntPermutationsGenerator g = new IntPermutationsGenerator(3);
while (g.hasNext()){
System.out.println(Arrays.toString(g.next()));
}
//gives
//[0, 1, 2]
//[0, 2, 1]
//[1, 0, 2]
//[1, 2, 0]
//[2, 0, 1]
//[2, 1, 0]
}
In the above code each subsequent permutation will be generated on the invocation of next()
while all other permutations will not be stored. Having such iterator you can just apply int[]
permutation to your array or list of objects.
You also can find the implementation of such iterator in redberry-core
package which available from Maven Central (see IntPermutationsGenerator).
The algorithm implemented in next()
generates permutations in lexicographic order. You can read more about this algorithm for example here.