Nach tagelangem Hickhack habe ich einen Algorithmus gefunden der Permutation mit der Effiziens O(n^2) erzeugt. Nach zahleichen Fehlschlägen ist mir die Wahrscheinlichkeitsrechnung wieder eingefallen, danach war die Lösung eigentlich offensichtlich.
Der entsprechende Algorithmus ist in der Methode permutate implementiert. Das Progrämmchen kann auch mit dem gcj kompiliert werden.
--- edit ---
Habe permutateSlow() entfernt weil die Methode nicht funktioniert.
--- edit2 ---
Teilweise int mit long ersetzt.
--- edit3 ---
Optimierungen.
--- edit4 ---
Neue Methode unPermutate().
Code:
/**
* This class contains methods to create permutations of arrays.
*
* @author kamikaze
* @version 1.00.2006.09.03
*/
public class Permutation {
/**
* Allows calling the permutate() method from the command line.
* The first parameter is the number of the wanted permutation, all
* following parameters will be treated as array elements.
*
* @param args The wanted permutation index and the array to
* create a permutation from.
*/
public static void main(String args[]) {
long permutation = Long.parseLong(args[0]);
String array[] = new String[args.length - 1];
for (int i = 0; i < array.length; i++)
array[i] = args[i + 1];
permutate(array, permutation);
for (int i = 0; i < array.length; i++)
System.out.print(array[i] + " ");
System.out.println();
}
/**
* Creates a permutation of an array. This method performs O(n^2).
*
* @param objects An array to create a permutation from.
* @param permutation A number defining which permutation is wanted.
*/
public static void permutate(Object objects[], long permutation) {
// A backup of the original array, required to build the new one.
Object original[] = (Object[]) objects.clone();
// Set all objects to null, to mark them as free.
for (int i = 0; i < objects.length; i++)
objects[i] = null;
// Assign a new position to every object.
for (int i = 0; i < objects.length; i++) {
// Get the position for this object.
int position = (int) (permutation % (objects.length - i));
// Lower permutation for the next object.
permutation /= objects.length - i;
// Find the free position.
int freePosition = 0;
for (;position > 0 || objects[freePosition] != null; freePosition++)
if (objects[freePosition] == null)
position--;
// Assign the position.
objects[freePosition] = original[i];
}
}
/**
* Undoes the permutation of an array.
*
* @param objects An array to turn into its original form.
* @param permutation A number defining which permutation the given
* array is.
*/
public static void unPermutate(Object objects[], long permutation) {
// A backup of the given array, required for the reconstruction.
Object permutated[] = (Object[]) objects.clone();
// An array containing its index numbers.
Integer order[] = new Integer[objects.length];
for (int i = 0; i < objects.length; i++)
order[i] = i;
// Permutate the index numbers as the original objects are permutated.
permutate(order, permutation);
// Restore the original order.
for (int i = 0; i < objects.length; i++)
objects[i] = permutated[order[i]];
}
}Der entsprechende Algorithmus ist in der Methode permutate implementiert. Das Progrämmchen kann auch mit dem gcj kompiliert werden.
--- edit ---
Habe permutateSlow() entfernt weil die Methode nicht funktioniert.
--- edit2 ---
Teilweise int mit long ersetzt.
--- edit3 ---
Optimierungen.
--- edit4 ---
Neue Methode unPermutate().
Zuletzt bearbeitet:
halt typisch C verwandt 
da hätte ich aber was viel kürzeres anzubieten: 
