Definition Permutation
Der Begriff "Permutation" beschreibt eine mögliche Anordnung von Elementen. Alle Permutationen einer Liste stellen unterschiedliche Varianten dar, wie die Elemente angeordnet werden können. Die Anzahl der Permutationen ohne Wiederholung lässt sich durch die Fakultät berechnen.
Beispiel:
Ausgangslage: Bob, Sandra und Peter müssen jeweils auf einem von drei Stühle sitzen.
Berechnung der Anzahl Anordnungen: \(n! => 3! = 3 \times 2 \times 1 = 6\)
Beweis:
- Sandra, Bob, Peter
- Sandra, Peter, Bob
- Bob, Sandra, Peter
- Bob, Peter, Sandra
- Peter, Sandra, Bob
- Peter, Bob, Sandra
Heap’s Algorithmus
Der Mathematiker Berge Heap entwickelte einen Algorithmus zur Erzeugung von Permutationen ohne Wiederholung.
Nachfolgend finden Sie Java-Code, der diesen Algorithmus in Verbindung mit dem obigen Beispiel demonstriert.
public class HeapPermutator {
public static void main(String[] args) {
HeapPermutator permutator = new HeapPermutator();
String[] people = new String[] {"Bob", "Sandra", "Peter"};
permutator.permutePeople(people);
}
public void permutePeople(String[] people) {
permutePeople(people, people.length);
}
private void permutePeople(String[] people, int range) {
if (range == 1) {
printPermutation(people);
return;
}
for (int 1 = @; i < range; i++) {
permutePeople(people, range - 1);
if (range % 2 == 0) {
swap(people, i, range - 1);
} else {
swap(people, 0, range - 1);
}
}
private void swap(String[] array, int from, int to) {
String temp = array[to];
array[to] = array[from];
array[from] = temp;
}
private void printPermutation(String[] permutation) {
System.out.println(String.join(", ", permutation));
}
}
DE 
EN