Outil pour calculer le rang d'une permutation d'un ensemble. Le rang d'une permutation est le numéro associé à celle-ci dans l'ordre de génération des permutations.
Rang d'une Permutation - dCode
Catégorie(s) : Combinatoire
dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les maths, les énigmes, les géocaches, et les problèmes à résoudre au quotidien !
Une suggestion ? un problème ? une idée ? Écrire à dCode !
Rang d'une Permutation
Calculer l'ordre d'une Permutation
Trouver une Permutation d'après son Rang/Ordre
Réponses aux Questions (FAQ)
Qu'est ce que le rang d'une permutation ? (Définition)
Le rang d'une permutation est un entier qui représente la position d'une permutation spécifique dans l'ordre lexicographique de toutes les permutations possibles d'un ensemble d'éléments distincts.
A partir de la liste de toutes les permutations possibles d'un ensemble (ou arrangements), il est possible de trier cet index par ordre croissant. Le rang d'une permutation est la position de celle-ci dans la liste triée.
Exemple : L'ensemble A,B,C a pour permutations :
| 0 | ABC |
| 1 | ACB |
| 2 | BAC |
| 3 | BCA |
| 4 | CAB |
| 5 | CBA |
Comment calculer le rang d'une permutation ?
Comme il semble difficile de lister toutes les permutations lorsqu'il y a beaucoup d'éléments. Il existe une méthode mathématique pour réaliser ce calcul.
Soit une permutation $ P $ dans l'ensemble $ E $ de taille $ t $.
Exemple : La permutation B,A,C dans l'ensemble initial A,B,C de taille $ t = 3 $.
Pour chaque lettre, calculer la position $ p $ dans l'ensemble $ E $, calculer $ s = p \times (t-1)! $ et retirer la lettre dans l'ensemble $ E $ (la taille $ t $ diminue). La somme des $ s $ est le rang de la permutation.
Exemple : B est en position $ 1 $ dans ABC, $ s_B = 1 \times 2! = 2 $
A est en position $ 0 $ dans AC, $ s_A = 0 \times 1! = 0 $
C est en position $ 0 $ dans C, $ s_C = 0 \times 0! = 0 $
BAC est la permutation de rang $ s_B + s_A + s_C = 2 + 0 + 0 = 2 $
Quel est l'algorithme de calcul du rang d'une permutation ?
Un code source qui calcule le rang dune permutation alphabétique serait : // Pseudo-code
function rankPermutation(p) {
alphabet = "abcdefghijklmnopqrstuvwxyz"
length = length(p)
rank = 0
j = 0
for i = length-1 down to 0 {
letter = p[j++]
index = position(letter, alphabet)
alphabet = alphabet[0..index] + alphabet[index+1..]
rank += index * factorial(i);
}
return rank;
}
Exemple : QWERTYUIOPASDFGHJKLZXCVBNM a pour rang lexicographique 261329910883437428257896643
Code source
dCode se réserve la propriété du code source pour "Rang d'une Permutation". Sauf code licence open source explicite (indiqué Creative Commons / gratuit), l'algorithme pour "Rang d'une Permutation", l'applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou les fonctions liées à "Rang d'une Permutation" (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codés en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) ou les données, en téléchargement, script, ou les accès API à "Rang d'une Permutation" ne sont pas publics, idem pour un usage hors ligne, PC, mobile, tablette, appli iPhone ou Android !
Rappel : dCode est gratuit.
Citation
Le copier-coller de la page "Rang d'une Permutation" ou de ses résultats est autorisée (même pour un usage commercial) tant que vous créditez dCode !
L'exportation des résultats sous forme de fichier .csv ou .txt est gratuite en cliquant sur l'icone export
Citer comme source bibliographique :
Rang d'une Permutation sur dCode.fr [site web en ligne], consulté le 21/05/2024,
