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 coollex!

Appears in Discrete Mathematics, 309 (2009) 53055320.

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) 570576.

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,
PreFascicle
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 kdegenerate Graphs,
Analytic Algorithmics and Combinatorics (ANALCO10), SIAM
proceedings, pp. 9098.

Yongxi Cheng,
Generating Combinations by Three Basic Operations,
Journal of Computer Science and Technology,
22 (2007) 909913.
Back to list of publications.