Abstract: Simple Combinatorial Gray Codes
Simple combinatorial Gray codes constructed by
reversing sublists
Frank Ruskey, Department of Computer Science,
University of Victoria, Canada.
Abstract:
We present three related results about simple combinatorial Gray
codes constructed recursively by reversing certain sublists.
First, we show a bijection between the
list of compositions of Knuth and the list of
combinations of Eades and McKay.
Secondly, we provide a short description of a list of combinations
satisfying a more restrictive closeness criteria of Chase.
Finally, we develop a new, simply described, Gray code list of the
partitions of a set into a fixed number of blocks, as represented
by restricted growth sequences.
In each case the recursive definition of the list is easily
translatable into an algorithm for generating
the list in time proportional to the number of elements in the
list; i.e., each object is produced in O(1) amortized
time by the algorithm.
 The postscript file is 135,573 bytes,
the dvi file is 28,424 bytes.
 Presented at Algorithms and Computation, 4th International Symposium,
ISAAC '93, Hong Kong, December 1993.
 Appeared in Lecture Notes in Computer Science, #762, 201208.
 Implementations are available.
 The algorithms are used in the
"Object Server",
in the set partitions section.
 The reference to the Knuth list is from the book: Herbert S. Wilf,
Combinatorial Algorithms: An Update, SIAM CBMS55, 1989.
 The reference to Eades and McKay is from the paper: P. Eades and B. McKay,
An Algorithm for Generating Subsets of Fixed Size with a Strong Minimal
Change Property, Information Processing Letters, 19 (1984) 131133.
Selected references that refer to this paper:

Hasan Sozer, Bedir Tekinerdogan, Mehmet Aksit,
FLORA: a framework for decomposing software architecture to introduce
local recovery, Software, Practice and Experience,
2009, DOI: 10.1002/spe.916.

O. Aichholzer, F. Aurenhammer, C. Huemer, B. Vogtenhuber,
Gray Code Enumeration of Plane StraightLine Graphs,
Graphs and Combinatorics, 23 (2007) 467479.

O. Aichholzer, F. Aurenhammer, C. Huemer, B. Vogtenhuber,
Gray Code Enumeration of Plane StraightLine Graphs,
22nd European Workshop on Computational Geometry,
EWCG 2006, Delphi, (2006) 7174.

C. Huemer, F. Hurtado, J. Pfeifle,
The Rotation Gray of kary Trees is Hamiltonian,
22nd European Workshop on Computational Geometry,
EWCG 2006, Delphi, (2006) 7578.

Jun Du, Reda Alhajj, and Ken Barker,
Genetic algorithms based approach to database vertical partition,
Journal of Intelligent Information Systems, Springer,
26 (2006) 167183.

Williams, Ryan,
A new algorithm for optimal 2constraint satisfaction and its
implications,
Theoretical Computer Science, 348 (2005), no. 23, 357365.

Baril, JeanLuc; Vajnovszki, Vincent,
Gray code for derangements,
Discrete Applied Mathematics, 140 (2004), no. 13, 207221.

Ryan Williams,
A new algorithm for optimal constraint satisfaction
and its applications,
Electronic Colloquium on Computational Complexity, Report No. 32 (2004),
ISSN 14338092.

Vincent Vajnovszki,
Gray visiting Motzkins,
Acta Informatica, 38 (2002) 793811.
Back to list of Frank Ruskey's publications.