serial number of combination

How can I find the serial number of an n-choose-k combination?

I would like a function that gets as input:

• $n$,

• $k$,

• a set of $k$ elements out of the set ${0, 1, ... n-1}$.

The output should be a number in the range $[0, C(n,k)-1]$, such that:

• Each different combination gets a different number;

• All numbers in the range are covered (i.e. no holes in the index).

For example, for $n=3$, $k=2$, the function could be:

$serial(3, 2, {a,b}) = (a+b-1)$

Since there are only 3 combinations, and their sum is different. Obviously, this doesn't generalize to larger n and k.

One solution is: at the beginning of the program, loop over all combinations, and create a static map from a combination to its index. However, this is very inefficient when n is large.

We will use the notation $\binom{n}{k}$ instead of your $C(n,k)$. The idea is to use Pascal's identity $$ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} $$ and its proof: there are $\binom{n-1}{k}$ not containing $n$, and $\binom{n-1}{k-1}$ containing $n$. Suppose we want to encode combinations not containing $n$ before combinations containing $n$. We work recursively. If the input set $S$ doesn't contain $n$, then we recurse on $S$ as a combination in $[n-1]$. If it does contain $n$, we recurse on $S \setminus \{n\}$ as a combination in $[n-1]$ (of size $k-1$), and add $\binom{n-1}{k}$ to the result.

Here is Python code for the procedure:

def encode(n, k, S):
    if n == 0:
        return 0
    if n not in S:
        return encode(n-1, k, S)
    S.remove(n)
    return encode(n-1, k-1, S) + choose(n-1, k)

The function choose (not supplied) should compute the Binomial coefficient. You can also decode the resulting code:

def decode(n, k, C):
    if n == 0:
        return []
    if C < choose(n-1, k):
        return decode(n-1, k, C)
    C -= choose(n-1, k)
    return decode(n-1, k-1, C) + [n]

StackExchange Computer Science Q#12574, answer score: 7