I have an array of instances from which I would like to produce all
possible permutations concerning the order as quickly as possible.
Before I go and implement that manually, maybe anyone has a hint for me
how this might be handled "best".
Below is some code that does it. There is a method for an int array and one
for a char array. As long as your objects implement the Comparable
interface (i.e., they have a compareTo method), you can easily adapt this
code by replacing things like
while (a[j] > a[k]) { ... }
with
while (a[j].compareTo(a[k]) > 0) { ... }
If your objects don't implement Comparable (and they have no natural
ordering), you can just arbitrarily assign them unique numbers and permute
them based on these numbers.
------------------- here's the code -------------------
import java.util.*;
// Permutation utility class. has nextPerm() methods for
// a char[], and int[].
// Adapted from Kenneth Rosen's discrete math book for programming contests.
public class Permutations {
public static int[] nextPerm(int[] arr) {
int[] a = (int[]) arr.clone();
int n = a.length-1;
int j = n - 1;
// "123, 132, 213, 231, 312, 321"
while (a[j] > a[j+1]) {
if (j==0) {
// last permutation - reset
int[] error = new int[] { 0 } ;
return error;
}
j--;
}
// j is the largest subscript with a[j] < a[j+1]
int k = n;
while (a[j] > a[k]) {
// sanity checking here
k--;
}
// a[k] is the smallest term greater than a[j] to the
// right of a[j] -- swap a[j] and a[k]
int tmp = a[j]; a[j] = a[k]; a[k] = tmp;
int r = n;
int s = j + 1;
while (r > s) {
// swap a[r] and a
tmp = a[r];
a[r] = a;
a = tmp;
r--;
s++;
}
return a;
}
public char[] nextPerm(char[] arr) {
char[] a = (char[]) arr.clone();
int n = a.length-1;
int j = n - 1;
// "123, 132, 213, 231, 312, 321"
while (a[j] > a[j+1]) {
if (j==0) {
// last permutation - reset
char[] error = new char[] { 0 } ;
return error;
}
j--;
}
// j is the largest subscript with a[j] < a[j+1]
int k = n;
while (a[j] > a[k]) {
// sanity checking here
k--;
}
// a[k] is the smallest term greater than a[j] to the
// right of a[j] -- swap a[j] and a[k]
char tmp = a[j]; a[j] = a[k]; a[k] = tmp;
int r = n;
int s = j + 1;
while (r > s) {
// swap a[r] and a
tmp = a[r];
a[r] = a;
a = tmp;
r--;
s++;
}
return a;
}
// factorial
public long fact(int n) {
int f = 1;
for (int i=1; i <= n; i++)
f *= i;
return f;
}
public static void main(String[] args) {
// test char array
char[] sc = "123456".toCharArray();
long n = p.fact(sc.length);
long start = System.currentTimeMillis();
System.out.println("char array Time = "+start);
System.out.println("Fact = "+n);
for (long i=0; i < n; i++) {
//System.out.println("sc = "+new String(sc));
sc = p.nextPerm(sc);
}
long end = System.currentTimeMillis();
System.out.println("Time = "+end+" -- elapsed = "+""+(end-start));
int[] ar = { 0,1,2,3 };
n = p.fact(ar.length);
for (long i=0; i < n; i++) {
System.out.print("ar = ");
for (int j=0; j < ar.length; j++)
System.out.print(ar[j]+", ");
System.out.println();
ar = p.nextPerm(ar);
}
}
}