I was wondering if there is an obvious way to 'name' the ${n \choose k}$ subsets of size $k$ of the integers from $1$ to $n$. So I am looking for a bijection from the subsets of $\{1,\ldots, n\}$ into $\{1, \ldots, {n \choose k}\}$ that can be computed in $O(1)$ at best.

The most trivial way for this would be to use a tree where each leaf node corresponds to such a subset but then I have to save the entire tree and each lookup will cost more than $O(1)$. We could also totally order those subsets such that $\{1, 2, 3\}$ would be the smallest subset for $k=3$ and $\{n, n-1, n-2\}$ the largest one and then use the number of smaller/equal subsets in this ordering as our index. I tried to come up with a closed form solution and it ended in some gnarly sums of binomial coefficients.

So maybe there is a well known solution to this problem and somebody could give me a reference?

up vote 0 down vote accepted

The bijection you are looking for is known as a combinatorial number system. A great further resource is Knuth's TAOCP.

  • Thank's a lot, that is exactly what I was looking for. – Maximal Nov 30 at 14:49
  • @Maximal You're welcome, and welcome to the site! – Juho Nov 30 at 14:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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