The Coolest Way to Generate Combinations

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

Abstract:

We present a practical and elegant method for generating all (s,t)-combinations (binary strings with s zeros and t ones): Identify the shortest prefix ending in 010 or 011 (or the entire string if no such prefix exists), and rotate it by one position to the right. This iterative rule gives an order to (s,t)-combinations that is circular and genlex. Moreover, the rotated portion of the string always contains at most four contiguous runs of 0s and 1s, so every iteration can be achieved by transposing at most two pairs of bits. This leads to an efficient loopless and branchless implementation that consists only of two variables and six assignment statements. The order also has a number of striking similarities to colex order, especially its recursive definition and ranking algorithm. In light of these similarities we have named our order cool-lex!

Appears in Discrete Mathematics, 309 (2009) 5305-5320.
The postscript file.
The pdf file.
Accepted (July 11, 2007) to appear in Discrete Mathematics (special issue on De Bruijn cycles and generalized Gray codes). Submitted September 6, 2006.
In press: link to Elsevier.
Preliminary version 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.
Here is the the C(6,3) output rendered musically: slow, fast.
These midi files were kindly created for us by George Tzanetakis.
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.
Here is a prolog program that implements coollex order (by Aaron Williams).
The open problem of listing combinations using the permutations (1 2), (1 2 ... n), (n ... 2 1) acting on the indices has been resolved (in the negative) by Yongxi Cheng, publication details below.

Selected Publications that refer to this paper:

Reinhard Bauer, Marcus Krug, and Dorothea Wagner, Enumerating and Generating Labeled k-degenerate Graphs, Analytic Algorithmics and Combinatorics (ANALCO10), SIAM proceedings, pp. 90-98.
Yongxi Cheng, Generating Combinations by Three Basic Operations, Journal of Computer Science and Technology, 22 (2007) 909-913.

Back to list of publications.