Rang d'une Permutation

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.

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 $.

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.

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;
}