Unranking of small combinations from large sets

An unranking algorithm for a finite set S is an algorithm that, given a number in {0,1,…,|S|−1}, returns an element of S that is associated with the number. We suppose that a number can be associated with any element in S so long as distinct elements are associated with different numbers. A ranking algorithm is the reverse of an unranking algorithm. In this paper, we present an unranking algorithm for the set of all m-element subsets of an n-element set. Our algorithm runs with O(m3m+3) arithmetic operations, which is independent of n and hence is effective when n is large. We also show that it admits a ranking algorithm with the same running time.