Tool to calculate the rank of a permutation of a set. The permutation's rank is the number associated with it in the order of generation of the permutations.
Rank of a Permutation - dCode
Tag(s) : Combinatorics
dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!
Rank of a Permutation
Permutation Order (Rank of a Word) Calculator
Find a Permutation from its Rank/Order
Answers to Questions (FAQ)
What is the rank of a permutation? (Definition)
The rank of a permutation is an integer that represents the position of a specific permutation in the lexicographic order of all possible permutations of a set of distinct elements.
From the list of all possible permutations of a set (or arrangements), it is possible to sort this index in ascending order. The rank of a permutation is the position of that if in the sorted list.
Example: The set A,B,C has for permutations:
| 0 | ABC |
| 1 | ACB |
| 2 | BAC |
| 3 | BCA |
| 4 | CAB |
| 5 | CBA |
How to calculate the rank of a permutation?
Since it seems difficult to list all permutations when there are many items. There is a mathematical method to perform this calculation.
Take a permutation $ P $ in the set $ E $ of size $ t $.
Example: The permutation B,A,C from the initial set A,B,C of size $ t = 3 $
For each letter, calculate the position $ p $ in the set $ E $, calculate $ s = p \times (t-1)! $ and remove the letter from the set $ E $ (size $ t $ decreases). The sum of $ s $ is the rank of the permutation.
Example: B is in position $ 1 $ in ABC, $ s_B = 1 \times 2! = 2 $
A is in position $ 0 $ in AC, $ s_A = 0 \times 1! = 0 $
C is in position $ 0 $ in C, $ s_C = 0 \times 0! = 0 $
BAC is at permutation rank $ s_B + s_A + s_C = 2 + 0 + 0 = 2 $
What is the algorithm for calculating the rank of a permutation?
A source code that calculates the rank of an alphabetical permutation would be:// 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;
}
Example: QWERTYUIOPASDFGHJKLZXCVBNM has for lexicographic rank 261329910883437428257896643
Source code
dCode retains ownership of the "Rank of a Permutation" source code. Any algorithm for the "Rank of a Permutation" algorithm, applet or snippet or script (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or any "Rank of a Permutation" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) or any database download or API access for "Rank of a Permutation" or any other element are not public (except explicit open source licence like Creative Commons). Same with the download for offline use on PC, mobile, tablet, iPhone or Android app.
Reminder: dCode is an educational and teaching resource, accessible online for free and for everyone.
Cite dCode
The content of the page "Rank of a Permutation" and its results may be freely copied and reused, including for commercial purposes, provided that dCode.fr is cited as the source.
Exporting the results is free and can be done simply by clicking on the export icons ⤓ (.csv or .txt format) or ⧉ (copy and paste).
To cite dCode.fr on another website, use the link:
In a scientific article or book, the recommended bibliographic citation is: Rank of a Permutation on dCode.fr [online website], retrieved on 2025-04-16,
