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

The copy-paste of the page "Combination Rank" 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):

*Combination Rank* on dCode.fr [online website], retrieved on 2024-09-14,

rank,combination,order,list

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

© 2024 dCode — El 'kit de herramientas' definitivo para resolver todos los juegos/acertijos/geocaching/CTF.

Feedback