Permutation
Une permutation compte les manières ordonnées de choisir k éléments parmi n, P(n,k)=n!/(n-k)! ; le nombre de permutations complètes est n!.
Objectif
Compter les sélections ordonnées, un fondement du dénombrement.
Mécanisme
P(n,k) = n!/(n-k)! = n×(n-1)×...×(n-k+1). Permutations complètes P(n,n)=n!. Avec répétition P(n,k)=n^k. Circulaires P(n,k)=(n-1)!. On génère toutes les permutations par retour sur trace ou l'algorithme de Heap.
Cas d’usage
- Génération et énumération de permutations
- Calcul de la robustesse des mots de passe
- Problèmes d'ordonnancement et de tri
- Calcul de probabilités
Exemples
- entrée
P(5,3)=5!/(5-3)!=60Output60Ordered arrangements of 3 out of 5
Erreurs courantes
- Confusing permutations with combinations (ordered vs unordered)
- Permutations are ordered (P), combinations unordered (C)
Termes associés
Combination
Une combinaison compte les façons de choisir k éléments parmi n sans tenir compte de l'ordre, C(n,k)=n!/(k!(n-k)!), c'est-à-dire le coefficient binomial. GLOSSAIRE
Factorial
La factorielle n! = n×(n-1)×...×1 fonde les permutations et combinaisons ; elle croît extrêmement vite, 20! dépassant déjà la plage des entiers 64 bits. GLOSSAIRE