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

dCode and you

dCode is free and its tools are a valuable help in games, puzzles and problems to solve every day!
You have a problem, an idea for a project, a specific need and dCode can not (yet) help you? You need custom development? Contact-me!


Team dCode likes feedback and relevant comments; to get an answer give an email (not published). It is thanks to you that dCode has the best Combination Rank tool. Thank you.

Combination Rank

Sponsored ads

Rank from Combination Calculator



Combination from Rank Calculator



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.

Answers to Questions

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 in 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{2}{4} \) is computed \( \binom{2}{4} - \binom {3}{2} - \binom{1}{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{2}{3} = 3 < r \) then \( \binom {2}{4} = 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)

Ask a new question

Source code

dCode retains ownership of the source code of the script Combination Rank online. Except explicit open source licence (indicated Creative Commons / free), any algorithm, applet, snippet, software (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt, encrypt, decipher, cipher, decode, code, translate) written in any informatic langauge (PHP, Java, C#, Python, Javascript, Matlab, etc.) which dCode owns rights will not be given for free. To download the online Combination Rank script for offline use on PC, iPhone or Android, ask for price quote on contact page !

Questions / Comments


Team dCode likes feedback and relevant comments; to get an answer give an email (not published). It is thanks to you that dCode has the best Combination Rank tool. Thank you.


Source : https://www.dcode.fr/combination-rank
© 2018 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaches. dCode
Feedback