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. Except explicit open source licence (indicated Creative Commons / free), the "Rank of a Permutation" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "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.) and all data download, script, or API access for "Rank of a Permutation" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!
Reminder : dCode is free to use.
Cite dCode
The copy-paste of the page "Rank of a Permutation" or any of its results, is allowed (even for commercial purposes) as long as you credit dCode!
Exporting results as a .csv or .txt file is free by clicking on the export icon
Cite as source (bibliography):
Rank of a Permutation on dCode.fr [online website], retrieved on 2024-11-21,
