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

Question

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 :-)

Answer 1

If you have a set of positive integers 0<=x_1 < x_2< ... < x_k , then you could use something called the squashed order:

I = sum(j=1..k) Choose(x_j,j)

The beauty of the squashed order is that it works independent of the largest value in the parent set.

The squashed order is not the order you are looking for, but it is related.

To use the squashed order to get the lexicographic order in the set of k-subsets of {1,...,n) is by taking

1 <= x1 < ... < x_k <=n

compute

 0 <= n-x_k < n-x_(k-1) ... < n-x_1

Then compute the squashed order index of (n-x_k,...,n-k_1)

Then subtract the squashed order index from Choose(n,k) to get your result, which is the lexicographic index.

If you have relatively small values of n and k, you can cache all the values Choose(a,b) with a

See Anderson, Combinatorics on Finite Sets, pp 112-119

Answer 2

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.