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 !
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 |
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 $
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
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.
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 05/10/2024,