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

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.

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:__ The combination rank (1,3) among the combinations $ \binom{4}{2} $ is computed $ \binom{4}{2} - \binom {3}{2} - \binom{1}{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 algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (PHP, Java, C#, Python, Javascript, Matlab, etc.) no data, script or API access will be for free, same for Combination Rank download for offline use on PC, tablet, iPhone or Android !

Please, check our community Discord for help requests!

rank,combination,permutation,order,list

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

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

Feedback

▲