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*!

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.

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)`

dCode retains ownership of the online "Combination Rank" tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any "Combination Rank" algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any "Combination Rank" function (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and no data download, script, copy-paste, or API access for "Combination Rank" will be for free, same for offline use on PC, tablet, iPhone or Android ! dCode is free and online.

Please, check our dCode Discord community for help requests!

NB: for encrypted messages, test our automatic cipher identifier!

rank,combination,order,list

Source : https://www.dcode.fr/combination-rank

© 2021 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback

▲
Thanks to your feedback and relevant comments, dCode has developed the best 'Combination Rank' tool, so feel free to write! Thank you!