Permutation
Eine Permutation zählt die geordneten Wege, k aus n Elementen zu wählen, P(n,k)=n!/(n-k)!; die Anzahl vollständiger Permutationen ist n!.
Zweck
Zählt geordnete Auswahlen, ein Grundlagenbegriff der Kombinatorik.
Mechanismus
P(n,k) = n!/(n-k)! = n×(n-1)×...×(n-k+1). Vollständige Permutationen P(n,n)=n!. Mit Wiederholung P(n,k)=n^k. Kreispermutationen P(n,k)=(n-1)!. Zur Erzeugung aller Permutationen dienen Backtracking oder Heaps Algorithmus.
Anwendungsfälle
- Erzeugung und Aufzählung von Permutationen
- Berechnung der Passwortstärke
- Planungs- und Reihenfolgeprobleme
- Wahrscheinlichkeitsberechnung
Beispiele
- Eingabe
P(5,3)=5!/(5-3)!=60Output60Ordered arrangements of 3 out of 5
Häufige Fehler
- Confusing permutations with combinations (ordered vs unordered)
- Permutations are ordered (P), combinations unordered (C)
Verwandte Begriffe
Combination
Eine Kombination zählt die Arten, k Elemente aus n ohne Berücksichtigung der Reihenfolge zu wählen, C(n,k)=n!/(k!(n-k)!), also der Binomialkoeffizient. GLOSSAR
Factorial
Die Fakultät n! = n×(n-1)×...×1 ist die Grundlage von Permutationen und Kombinationen; sie wächst extrem schnell, 20! überschreitet bereits den 64-Bit-Integer-Bereich. GLOSSAR