# Linear ordering of all subsets of size k

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?

## 1 Answer

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 '18 at 14:49
• @Maximal You're welcome, and welcome to the site! – Juho Nov 30 '18 at 14:56