Cheap and Secure Web Hosting Provider : See Now

# [Solved]: serial number of combination

, ,
Problem Detail:

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.

#### Answered By : Yuval Filmus

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] ``

Question Source : http://cs.stackexchange.com/questions/12574

3.2K people like this