4
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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]
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.