Combination Rank

The rank of a combination corresponds to its position in the list of all possible combinations, sorted by ascending lexicographic order. On this page, dCode indexes the rank starting from $ 1 $.

For a combination of $ k $ elements denoted $ (c_1, c_2, \cdots, c_k) $ with $ 1 \le c_1 < c_2 < \cdots < c_k \le n $. The rank $ r $ of this combination among all the combinations of $ k $ elements chosen from $ n $ can be calculated without enumerating them using the formula: $$ r = \binom{n}{k} - \binom{n-c_1}{k} - \binom{n-c_2}{k-1} - \cdots - \binom{n-c_k}{1} $$

This formula is based on the counting of all combinations that are lexicographically larger than the combination studied.

The algorithm is based on the inverse principle of rank calculation: it consists of gradually reconstructing the elements of the combination using binomial coefficients.

For a combination of size $ k $ and a rank $ r $:

1 - Initialize an empty list for the combination

2 - For each position $ j $ ranging from $ k $ to $ 1 $, determine the largest integer $ c $ such that $ \binom{c}{j} < r $

3 - Add $ c + 1 $ at the beginning of the combination.

4 - Update the rank: $ r = r - \binom{c}{j} $

5 - Repeat steps 2, 3, and 4 for each value of $ j $, decrementing $ j $ by $ 1 $ at each iteration, until reaching $ j = 1 $