Tool for calculating the rank of a mathematical combination (or conversely, calculating a combination from a rank), that is, the position of a combination in the growing list of possible combinations generated.
Combination Rank - 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!
Combination Rank
Rank from Combination Calculator
Combination from Rank Calculator
Answers to Questions (FAQ)
How to calculate the rank of a combination?
The rank of a combination is the position of a combination in the list of all possible combinations sorted by ascending order.
Example: All combinations of 4 choose 2 are: (1,2),(1,3),(1,4),(2,3),(2,4),(3,4), therefore the rank of the combination (1,2) is 1, the rank of the combination (2,4) is 5
With $ c_i $ the elements in increasing order $ c_1, c_2, \cdots, c_k $ of a combination of $ k $ elements among $ n $ the total number of elements, the formula for calculate rank without listing all combinations is $$ \binom{n}{k} - \binom{n-c_1}{k} - \binom{n-c_2}{k-1} - \cdots - \binom{n-c_k}{1} $$
Example: Calculate the combination rank (1,3) among the combinations of 2 among 4 $ \binom{4}{2} $, is taking $ n = 4, k = 2, c_1 = 1, c_2 = 3 $ and calculate $$ \binom{4}{2} - \binom{4-1}{2} - \binom{4-3}{2-1} = 6 - 3 - 1 = 2 $$ so (1,3) is at rank 2.
How to calculate a combination from its rank?
This method calculates the minimal combination minimizing $ n $ (ie, with the smallest numbers) for a given size $ k $.
To compute a combination from a rank $ r $, knowing the number of element $ k $ of the combination, repeat the following algorithm:
1 - Calculate the largest number $ i $, such that the number of combinations $ \binom{k}{i} $ is less than or equal to the rank $ r $.
2 - Add $ i $ at the beginning of the combination, subtract the value $ \binom{k}{i} $ from $ r $ and decrement $ k $ by $ 1 $
3 - Repeat steps 1 and 2 as long as $ k > 0 $
Example: For a rank $ r = 5 $ and a combination of $ k = 2 $ elements
Step 1 - calculate $ \binom{2}{2} = 1 < r $, $ \binom{3}{2} = 3 < r $ then $ \binom {4}{2} = 6 > r $
Step 2 - Combination = (4), $ r = 5-3 = 2 $, $ k = 1 $
Step 1' - calculate $ \binom{1}{2} = 2 <= r $
Step 2' - Combination = (2,4) , $ r = 1 $, $ k = 0 $ - End
So the minimal combination of size 2 and rank 5 is (2,4)
Source code
dCode retains ownership of the "Combination Rank" source code. Except explicit open source licence (indicated Creative Commons / free), the "Combination Rank" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "Combination Rank" 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 "Combination Rank" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!
Reminder : dCode is free to use.
Cita dCode
The copy-paste of the page "Combination Rank" or any of its results, is allowed (even for commercial purposes) as long as you cite dCode!
Exporting results as a .csv or .txt file is free by clicking on the export icon
Cite as source (bibliography):
Combination Rank on dCode.fr [online website], retrieved on 2024-04-20,
