Cheap and Secure Web Hosting Provider : See Now

[Solved]: serial number of combination

, , No Comments
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.

Asked By : Erel Segal-Halevi

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] 
Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback