How to calculate the index (lexicographical order) when the combination is given

Here is a snippet that will do the work.

#include <iostream>

int main()
{
    const int n = 10;
    const int k = 5;

    int combination[k] = {2, 5, 7, 8, 10};

    int index = 0;
    int j = 0;
    for (int i = 0; i != k; ++i)
    {
        for (++j; j != combination[i]; ++j)
        {
            index += c(n - j, k - i - 1);
        }
    }

    std::cout << index + 1 << std::endl;

    return 0;
}

It assumes you have a function

int c(int n, int k);

that will return the number of combinations of choosing k elements out of n elements.
The loop calculates the number of combinations preceding the given combination.
By adding one at the end we get the actual index.

For the given combination there are
c(9, 4) = 126 combinations containing 1 and hence preceding it in lexicographic order.

Of the combinations containing 2 as the smallest number there are

c(7, 3) = 35 combinations having 3 as the second smallest number

c(6, 3) = 20 combinations having 4 as the second smallest number

All of these are preceding the given combination.

Of the combinations containing 2 and 5 as the two smallest numbers there are

c(4, 2) = 6 combinations having 6 as the third smallest number.

All of these are preceding the given combination.

Etc.

If you put a print statement in the inner loop you will get the numbers
126, 35, 20, 6, 1.
Hope that explains the code.

Leave a Comment