Search for a tool
Combination Rank

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.

Results

Combination Rank -

Tag(s) : Combinatorics

Share
Share
dCode and more

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!


Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!


Feedback and suggestions are welcome so that dCode offers the best 'Combination Rank' tool for free! Thank you!

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.

Cite dCode

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-06-14, https://www.dcode.fr/combination-rank

Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Questions / Comments

Feedback and suggestions are welcome so that dCode offers the best 'Combination Rank' tool for free! Thank you!


https://www.dcode.fr/combination-rank
© 2024 dCode — El 'kit de herramientas' definitivo para resolver todos los juegos/acertijos/geocaching/CTF.
 
Feedback