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

I know that there is an algorithm that permits, given a combination of number (no repetitions, no order), calculates the index of the lexicographic order.
It would be very useful for my application to speedup things...

For example:

combination(10, 5)  
1 - 1 2 3 4 5  
2 - 1 2 3 4 6  
3 - 1 2 3 4 7  
....  
251 - 5 7 8 9 10  
252 - 6 7 8 9 10  

I need that the algorithm returns the index of the given combination.
es: index( 2, 5, 7, 8, 10 ) --> index

EDIT: actually I'm using a java application that generates all combinations C(53, 5) and inserts them into a TreeMap. My idea is to create an array that contains all combinations (and related data) that I can index with this algorithm.
Everything is to speedup combination searching. However I tried some (not all) of your solutions and the algorithms that you proposed are slower that a get() from TreeMap.
If it helps: my needs are for a combination of 5 from 53 starting from 0 to 52.

Thank you again to all :-)

Solution 1:

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.

Solution 2:

Convert your number selections to a factorial base number. This number will be the index you want. Technically this calculates the lexicographical index of all permutations, but if you only give it combinations, the indexes will still be well ordered, just with some large gaps for all the permutations that come in between each combination.

Edit: pseudocode removed, it was incorrect, but the method above should work. Too tired to come up with correct pseudocode at the moment.

Edit 2: Here's an example. Say we were choosing a combination of 5 elements from a set of 10 elements, like in your example above. If the combination was 2 3 4 6 8, you would get the related factorial base number like so:

Take the unselected elements and count how many you have to pass by to get to the one you are selecting.

1 2 3 4 5 6 7 8 9 10
2 -> 1
1 3 4 5 6 7 8 9 10
3 -> 1
1 4 5 6 7 8 9 10
4 -> 1
1 5 6 7 8 9 10
6 -> 2
1 5 7 8 9 10
8 -> 3

So the index in factorial base is 1112300000

In decimal base, it's

1*9! + 1*8! + 1*7! + 2*6! + 3*5! = 410040