Abstract: Simple Combinatorial Gray Codes

Simple combinatorial Gray codes constructed by reversing sublists

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


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.

Selected references that refer to this paper:
Back to list of Frank Ruskey's publications.