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

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

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,
PreFascicle 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
AddisonWesley, 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.