Simple combinatorial Gray codes constructed by reversing sublists

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, 201-208.
• 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 CBMS-55, 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) 131-133.

• 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 Straight-Line Graphs, Graphs and Combinatorics, 23 (2007) 467-479.
• O. Aichholzer, F. Aurenhammer, C. Huemer, B. Vogtenhuber, Gray Code Enumeration of Plane Straight-Line Graphs, 22nd European Workshop on Computational Geometry, EWCG 2006, Delphi, (2006) 71-74.
• C. Huemer, F. Hurtado, J. Pfeifle, The Rotation Gray of k-ary Trees is Hamiltonian, 22nd European Workshop on Computational Geometry, EWCG 2006, Delphi, (2006) 75-78.
• Jun Du, Reda Alhajj, and Ken Barker, Genetic algorithms based approach to database vertical partition, Journal of Intelligent Information Systems, Springer, 26 (2006) 167-183.
• Williams, Ryan, A new algorithm for optimal 2-constraint satisfaction and its implications, Theoretical Computer Science, 348 (2005), no. 2-3, 357-365.
• Baril, Jean-Luc; Vajnovszki, Vincent, Gray code for derangements, Discrete Applied Mathematics, 140 (2004), no. 1-3, 207-221.
• Ryan Williams, A new algorithm for optimal constraint satisfaction and its applications, Electronic Colloquium on Computational Complexity, Report No. 32 (2004), ISSN 1433-8092.
• Vincent Vajnovszki, Gray visiting Motzkins, Acta Informatica, 38 (2002) 793-811.