Algorithms, Vol. 15, Pages 36: Unranking Small Combinations of a Large Set in Co-Lexicographic Order (Algorithms)

The presented research is devoted to the problem of developing new combinatorial generation algorithms for combinations. In this paper, we develop a modification of Ruskey’s algorithm for unranking m-combinations of an n-set in co-lexicographic order. The proposed modification is based on the use of approximations to make a preliminary search for the values of the internal parameter k of this algorithm. In contrast to the original algorithm, the obtained algorithm can be effectively applied when n is large and m is small because the running time of this algorithm depends only on m. Furthermore, this algorithm can be effectively used when n and m are both large but n−m is small, since we can consider unranking (n−m)-combinations of an n-set. The conducted computational experiments confirm the effectiveness of the developed modification.