Get a fixed-size family of k-element subsets

Question

I have an n-element set, and I want to consider families of its k-element subsets of fixed size s. For example, if n = 3, k = 1, s = 2, we have these families:

{{1}, {2}}, {{1}, {3}}, {{2}, {3}}

In my problem n, k, s are not so small, e.g. s = n = 50, k = 20.

Let us say all such families are ordered lexicographically (or really in any clearly stated order). I want to have an efficient way to get a family by its number.

I have only a following idea: enumerate all k-element subsets of n-element set (there is an efficient algorithm to get i-th element by i). Then enumerate all s-element subsets of comb(n, k)-element set, using the same operation. Now we need to generate a number in range (0, comb(comb(n, k), s)) and turn it firstly to the number of s-element subset and then to a family of k-elements sets.

However, I want to know, if there is a more beautiful approach than just generating first combination and then second combination by its numbers.

Answer 1

In general, what you are looking for is a combinatorial number system (of degree $t$) , i.e., a correspondece between $\mathbb{N}$ and all $t$-combinations.

There is a large number of algorithms for $t$-combination generation from the last (at least) 50 years. In particular, the operations you are interested in are typically called rank and unrank.

For much more than what the Wikipedia article contains at the time of writing, you can have a look at say the book of Knuth [1] or the one by Kreher and Stinson [2]. Knuth's book contains pseudocode that is straightforward to write in your favorite language, and the nook of Kreher and Stinson is accompanied by source code (in C) that can be found online as well.

---

[1] Knuth, Donald E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Pearson Education India, 2011.

[2] Kreher, Donald L., and Douglas R. Stinson. Combinatorial algorithms: generation, enumeration, and search. Vol. 7. CRC press, 1998.