Generating combinations by prefix shifts

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
Aaron Williams, Department of Computer Science, University of Victoria, Canada.

Abstract:

We present a new Gray code for combinations that is practical and elegant. We represent combinations as bitstrings with s 0's and t 1's, and generate them with a remarkably simple rule: Identify the shortest prefix ending in 010 or 011 (or the entire bitstring if no such prefix exists) and then rotate (shift) it by one position to the right. Since the rotated portion of the string consists of at most four contiguous runs of 0's and 1's, each successive combination can be generated by transposing only one or two pairs of bits. This leads to a very efficient loopless implementation. The Gray code also has a simple and efficient ranking algorithm that closely resembles that of combinations in colex order. For this reason, we have given a nickname to our order: cool-lex!

The postscript file.
The pdf file.
Appears as: F. Ruskey and A. Williams, Generating combinations by prefix shifts, COCOON 2005, The Eleventh International Computing and Combinatorics Conference, Kunming, China, 2005. Lecture Notes in Computer Science, 3595 (2005) 570-576.
An expanded journal version may be found here.
Here is the the C(6,3) output rendered musically: slow, fast.
These midi files were kindly created for us by George Tzanetakis.
Here is Don Knuth's MMIX implementation of the algorithms: Coolcomb.mms.

References to this paper:

The algorithm described in this paper appears in Donald E. Knuth, Volume 4 of the Art of Computer Programming, Pre-Fascicle 3a: Generating all combinations, in versions appearing in 2005 and later. In particular, it now appears in Volume 4, Fascicle 3, and is published by Addison-Wesley, 2006.
J. R. Snape, Loopless Functional Algorithms, Master's thesis, University of Oxford, Oxford, U.K., 2005.
Jörg Arndt, Algorithms for Programmers, 2008. Section 6.2 is devoted to Coollex order.
Yongxi Cheng, On Generating Combinations by Prefix Shifts (1 2), (1 2 ... n) and (n ... 2 1), Journal of Computer Science and Technology (JCST), to appear. (In this paper he answers our question about whether combinations can be generated by the three operations given in the title of his paper.)

Back to list of publications.