A Survey of Combinatorial Gray Codes.
The term combinatorial Gray code was introduced in 1980 to refer to any method for generating combinatorial objects so that successive objects differ in some prespecified, small way. This notion generalizes the classical binary reflected Gray code scheme for listing n-bit binary numbers so that successive numbers differ in exactly one bit position, as well as work in the 1960s and 1970s on minimal change listings for other combinatorial families, including permutations and combinations.The area of combinatorial Gray codes was popularized by Herbert Wilf in his invited address at the SIAM Conference on Discrete Mathematics in 1988 and his subsequent SIAM monograph [Combinatorial Algorithms: An Update, 1989] in which he posed some open problems and variations on the theme.  This resulted in much recent activity in the area, and most of the problems posed by Wilf are now solved.In this paper, we survey the area of combinatorial Gray codes, describe recent results, variations, and trends, and highlight some open problems.
Introduction
One of the earliest problems addressed in the area of combinatorial algorithms was that of
efficiently generating items in a particular combinatorial class in such a way that each item is
generated exactly once. Many practical problems require for their solution the sampling of a
random object from a combinatorial class or, worse, an exhaustive search through all objects
in the class. Whereas early work in combinatorics focused on counting, by 1960, it was clear
that with the aid of a computer it would be feasible to list the objects in combinatorial
classes [Leh64]. However, in order for such a listing to be possible, even for objects of
moderate size, combinatorial generation methods must be extremely efficient. A common
approach has been to try to generate the objects as a list in which successive elements
differ only in a small way. The classic example is the binary reflected Gray code [Gil58,
Gra53] which is a scheme for listing all n-bit binary numbers so that successive numbers
differ in exactly one bit. The advantage anticipated by such an approach is two-fold.
First, generation of successive objects might be faster. Although for many combinatorial
families, a straightforward lexicographic listing algorithm requires only constant average
time per element, for other families, such as linear extensions, such performance has only
been achieved by a Gray code approach [PR94]. Secondly, for the application at hand, it is
likely that combinatorial objects which differ in only a small way are associated with feasible
solutions which differ by only a small computation. For example in [NW78], Nijenhuis and
show how to use a binary Gray code to speed up computation of the permanent. Aside
from computational considerations, open questions in several areas of mathematics can be
posed as Gray code problems. Finally, and perhaps one of the main attractions of the area,
Gray codes typically involve elegant recursive constructions which provide new insights into
the structure of combinatorial families.
The term combinatorial Gray code first appeared in [JWW80] and is now used to refer
to any method for generating combinatorial objects so that successive objects differ in some
pre-specified, usually small, way. However, the origins of minimal change listings can be
found in the early work of Gray [Gra53], Wells [Wel61], Trotter [Tro62], Johnson [Joh63],
Lehmer [Leh65], Chase [Cha70], Ehrlich [Ehr73], and Nijenhuis and Wilf [NW78], and in the
work of campanologists [Whi83]. In his article on the origins of the binary Gray code, Heath
describes a telegraph invented by Emile Baudot in 1878 which used the binary reflected Gray
code [Hea72]. (According to Heath, Baudot received a gold medal for his telegraph at the
Universal Exposition in Paris in 1978, as did Thomas Edison and Alexander Graham Bell.)
Examples of combinatorial Gray codes include (1) listing all permutations of
that consecutive permutations differ only by the swap of one pair of adjacent elements
[Joh63, Tro62], (2) listing all k-element subsets of an n-element set in such a way that consecutive
sets differ by exactly one element [BER76, BW84, EHR84, EM84, NW78, Rus88a],
(3) listing all binary trees so that consecutive trees differ only by a rotation at a single node
[Luc87, LRR93], (4) listing all spanning trees of a graph so that successive trees differ only
by a single edge [HH72, Cum66] (5) listing all partitions of an integer n so that in successive
partitions, one part has increased by one and one part has decreased by one [Sav89], (6)
listing the linear extensions of certain posets so that successive elements differ only by a
transposition [Rus92, PR91, Sta92, Wes93], and (7) listing the elements of a Coxeter group
so that successive elements differ by a reflection [CSW89].
Gray codes have found applications in such diverse areas as circuit testing [RC81], signal
encoding [Lud81], ordering of documents on shelves [Los92], data compression [Ric86],
statistics [DH94], graphics and image processing [ASD90], processor allocation in the hyper-cube
hashing [Fal88], computing the permanent [NW78], information storage and
retrieval [CCC92], and puzzles, such as the Chinese Rings and Towers of Hanoi [Gar72].
In recent variations on combinatorial Gray codes, generation problems have been considered
in which the difference between successive objects, although fixed, is not required to
be small. An example is the problem of listing all permutations of so that consecutive
permutations differ in every location [Wil89]. The problem of generating all objects in a
combinatorial class, each exactly once, so that successive objects differ in a pre-specified
way, can be formulated as a Hamilton path/cycle problem: the vertices of the graph are
the objects themselves, two vertices being joined by an edge if they differ from each other
in the pre-specified way. This graph has a Hamilton path if and only if the required listing
of combinatorial objects exists. A Hamilton cycle corresponds to a cyclic listing in which
the first and last items also differ in the pre-specified way. But since the problem of determining
whether a given graph has a Hamilton path or cycle is NP-complete [GJ79], there
is no efficient general algorithm for discovering combinatorial Gray codes.
Frequently in Gray code problems, however, the associated graph possesses a great deal
of symmetry. Specifically, it may belong to the class of vertex transitive graphs. A graph
G is vertex transitive if for any pair of vertices u, v of G, there is an automorphism OE of G
with v. For example, permutations differing by adjacent transpositions give rise to
a vertex transitive graph, as do k-subsets of an n-set differing by one element. It is a well-known
open problem, due to Lov'asz, whether every undirected, connected, vertex transitive
graph has a Hamilton path [Lov70]. Thus, schemes for generating combinatorial Gray codes
in many cases provide new examples of vertex transitive graphs with Hamilton paths or
cycles, from which we hope to gain insight into the more general open questions. It is also
unknown whether all connected Cayley graphs (a subclass of the vertex transitive graphs)
are hamiltonian. For many Gray code problems, especially those involving permutations,
the associated graph is a Cayley graph.
Although many Gray code schemes seem to require strategies tailored to the problem at
hand, a few general techniques and unifying structures have emerged. The paper [JWW80]
considers families of combinatorial objects, whose size is defined by a recurrence of a particular
form, and some general results are obtained about constructing Gray codes for these
families. Ruskey shows in [Rus92] that certain Gray code listing problems can be viewed
as special cases of the problem of listing the linear extensions of an associated poset so
that successive extensions differ by a transposition. In the other direction, the discovery
of a Gray code frequently gives new insight into the structure of the combinatorial class
involved.
So, the area of combinatorial Gray codes includes many questions of interest in com-
binatorics, graph theory, group theory, and computing, including some well-known open
problems. Although there has been steady progress in the area over the past fifteen years,
the recent spurt of activity can be traced to the invited address of Herbert Wilf at the
SIAM Conference on Discrete Mathematics in San Francisco in June 1988, Generalized
Gray Codes, in which Wilf described some results and open problems. (These are also reported
in his SIAM monograph [Wil89].) All of the open problems on Gray codes posed
by Wilf in [Wil89] have now been solved, as well as several related problems, and it is our
intention here to follow up on this work. In this paper, we give a brief survey of the area
of combinatorial Gray codes, describe recent results, variations and trends, and highlight
some (new and old) open problems.
This paper is organized into sections as follows: 1. Introduction; 2. Binary Numbers
and Variations; 3. Permutations; 4. Subsets, Combinations, and Compositions; 5. Integer
Partitions; 6. Set Partitions and Restricted Growth Functions; 7. Catalan Families; 8.
Necklaces and Variations; 9. Linear Extension of Posets; 10. Acyclic Orientations; 11.
Cayley Graphs and Permutation Gray Codes; 12. Generalizations of de Bruijn Sequences;
13. Concluding Remarks.
In the remainder of this section, we discuss some notation and terminology which will
be used throughout the paper.
A Gray code listing of a class of combinatorial objects will be called max-min if the
first element on the list is the lexicographically largest in the class and the last element is
the lexicographically smallest. The Gray code is cyclic if the first and last elements on the
list differ in the same way prescribed for successive elements of the list by the adjacency
criterion.
In many situations, the graph associated with a particular adjacency criterion is bipar-
tite. If the sizes of the two partite sets differ by more than one, the graph cannot have a
Hamilton cycle and thus there is no Gray code listing of the objects corresponding to the
vertices, at least for the given adjacency criterion. In this case, we say that a parity problem
exists.
An algorithm to exhaustively list elements of a class C is called loop-free if the worst
case time delay between listing successive elements is constant; the algorithm is called
if, after listing the first element, the total time required by the algorithm to list all elements
is O(N ), where N is the total number of elements in the class C. The term CAT was coined
a. Binary Reflected b. Balanced c. Maximum Gap d. Non-composite
00000 11000 00000 10111 00000 00101 00000 01001
01000 10000 00111 00100 00111 00010 01011 00010

Figure

1: Examples of 5-bit binary Gray codes.
by Frank Ruskey to stand for constant amortized time per element.
Finally, we note that a Gray code for a combinatorial class is intrinsically bound to the
representation of objects in the class. If sets A and B are two alternative representations
of a class C under the bijections ff B, the closeness of ff(x) and
ff(y) need not imply closeness of fi(x) and fi(y). That is, Gray codes are not necessarily
preserved under bijection. Examples of this will be seen for several families, including
integer partitions, set partitions, and Catalan families.
Binary Numbers and Variations
A Gray code for binary numbers is a listing of all n-bit numbers so that successive
numbers (including the first and last) differ in exactly one bit position. The best known
example is the binary reflected Gray code [Gil58, Gra53] which can be described as follows.
If L n denotes the listing for n-bit numbers, then L 1 is the list 0, 1; for n ? 1, L n is formed
by taking the list for L n\Gamma1 and pre-pending a bit of '0' to every number, then following that
list by the reverse of L n\Gamma1 with a bit of '1' prepended to every number. So, for example,
shown in Figure 1(a).
Since the first and last elements of L n also differ in one bit position, the code is in fact a
cycle. It can be implemented efficiently as a loop-free algorithm [BER76]. Note that a
binary Gray code can be viewed as a Hamilton cycle in the n-cube.
In practice, Gray codes with certain additional properties may be desirable (see [GLN88]
for a survey). For example, note that as the elements of L n are scanned, the lowest order
times, whereas the highest order bit changes only twice, counting
the return to the first element. In certain applications, it is necessary that the number
of bit changes be more uniformly distributed among the bit positions, i.e., a balanced Gray
code is required. (See Figure 1(b) for an example from [VS80].) Uniformly balanced Gray
codes were shown to exist for n a power of two by Wagner and West [WW91]. For general
were suggested, but not proved, in [LS81, VS80, RC81].
Recently we have shown, using the Robinson-Cohn construction [RC81], that balanced
Gray codes exist for all n in the following sense: Let a = b2 n =nc or b2 n =nc \Gamma 1, so that a is
even. For each n ? 1 there is a cyclic n-bit Gray code in which each bit position changes
either a or a
In other applications, the requirement is to maximize the gap in a Gray code, which is
defined in [GLN88] to be the shortest maximal consecutive sequence of 0's (or 1's) among
all bit positions. (See Figure 1(c) for an example from [GLN88] in which the gap is 4, which
is best possible for report a construction in which GAP(n)/n
goes to 1 as n goes to infinity [GG]. Another variation, non-composite n-bit Gray codes,
requires that no contiguous subsequence correspond to a path in any k-cube for
Non-composite Gray codes have been constructed for all n [Ram90]. (See Figure 1(d) for
an example from [Ram90].)
A new constraint is considered in [SW95]. Define the density of a binary string to be
the number of 1's in the string. Clearly, no Gray code for binary strings can list them in
non-decreasing order of density. However, suppose the requirement is relaxed somewhat.
Call a Gray code monotone if it runs through the density levels two at a time, that is,
consecutive pairs of strings of densities those of densities
Figure

2: A monotone Gray code for
n. It is shown in [SW95] that monotone Gray codes can be constructed for all
n. An example for shown in Figure 2.
be the Boolean lattice of subsets of the set
inclusion, and let H n denote the Hasse diagram of B n . The correspondence
ng
is a bijection from n-bit binary numbers to subsets of [n] and, under this bijection, a binary
Gray code corresponds to a Hamilton path in H n .
The vertices of H n can be partitioned into level sets, contains
all of the i-element subsets of [n]. Then, a monotone Gray code is a Hamilton path in H n
in which edges between levels i and must precede edges between levels j and

Figure

3.)
Monotone Gray codes have applications to the theory of interconnection networks, providing
an embedding of the hypercube into a linear array which minimizes dilation in both
directions [SW95]. In Section 4 we discuss their relationship to the middle two levels problem

Fix a binary string ff and let B(n; ff) be the set of clean words for ff, i.e., the n-bit
strings which do not contain ff as a contiguous substring. Does the subgraph of the n-cube
induced by B(n; ff) have a Hamilton path, i.e., is there a Gray code for B(n; ff)? Squire has
shown that the answer is yes if ff can be written as is a string with
the property that no nontrivial prefix of fi is also a suffix of fi; otherwise there are parity
@
@ @
@
@
@ @\Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi
\Gamma\Phi \Phi \Phi \Phi \Phi \Phi \Phi \Phi \Delta

Figure

3: The Hamilton path in H 5 corresponding to the monotone Gray code in Figure 2.
problems for infinitely many n [Squ96].
It is natural to consider an extension of binary Gray codes to m-ary Gray codes. It was
shown in [JWW80], using a generalization of the binary reflected Gray code scheme, that
it is always possible to list the Cartesian product of finite sets so that successive elements
differ only in one coordinate. A similar result is obtained in [Ric86] where each coordinate
i is allowed to assume values in some fixed range results
on clean words to m-ary Gray codes [Squ96], but leaves open the case when m is odd.
Another listing problem for binary numbers, posed by Doug West, involves a change
in the underlying graph. View an n-bit string as a subset of ng under the natural
bijection g. Call two sets adjacent if they differ only in that
one element increases by 1, one element decreases by 1, or the element '1' is deleted. The
problem is to determine whether there is a Hamilton path in the corresponding graph, called
the augmentation graph. When n(n \Gamma 1)=2 is even, a parity argument shows there is no
Hamilton path. Otherwise, the question is open for n ? 7.
Consider another criterion: two binary strings are adjacent if they differ either by (1)
a rotation one position left or right or (2) by a negation of the last bit. The underlying
graph is the shuffle-exchange network and a Hamilton path would be a "Gray code" for
binary strings respecting this adjacency criterion. The existence of a Hamilton path in the
shuffle-exchange graph, a long-standing open problem, was recently established by Feldman
and Mysliwietz [FM93].
In [Fre79], Fredman considers complexity issues involved in generating arbitrary subsets
of the set of n-bit strings so that successive strings differ only in one bit. He calls these
quasi-Gray codes and establishes bounds and trade-offs on the resources required to generate
successors using a decision assignment tree model of computation.
Permutations
Algorithms for generating all permutations of
surveyed by Sedgewick in [Sed77]. Efficiency considerations provided the motivation for
several early attempts to generate permutations in such a way that successive permutations

Figure

4: Johnson-Trotter scheme for generating permutations by adjacent transpositions.

Figure

5: Generating permutations by derangements, due to Lynn Yarbrough.
differ only by the exchange of two elements. Such a Gray code for permutations was shown to
be possible in several papers, including [Boo65, Boo67, Hea63, Wel61], which are described
in [Sed77]. One disadvantage of these algorithms is that the elements exchanged are not
necessarily in adjacent positions.
It was shown independently by Johnson [Joh63] and Trotter [Tro62] that it is possible
to generate permutations by transpositions even if the two elements exchanged are required
to be in adjacent positions. The recursive scheme, illustrated in Figure 4, inserts into each
permutation on the list for the element 'n' in each of the n possible positions, moving
alternately from right to left, then left to right.
A contrary approach to the problem is to require that permutations be listed so that each
one differs from its predecessor in every position, that is, by a derangement. This problem
was posed independently in [Rab84, Wil89]. The existence of such a list when n 6= 3
was established in [Met85] using Jackson's theorem [Jac80] and a constructive solution was
presented in [EW85]. A simpler construction, ascribed to Lynn Yarbrough, is discussed
in [RS87]. Yarbrough's solution is illustrated in Figure 5 and works as follows. Take
each permutation on the Johnson-Trotter list for append an 'n', and rotate the
resulting permutation, one position at a time, through its n possible cyclic shifts. As a
final twist, swap the last two cyclic shifts. It is straightforward to argue that successive
permutations differ in every position, using the property of the Johnson-Trotter list that
successive permutations differ by adjacent transpositions.
To generalize the problems of generating permutations, at one extreme, by adjacent
transpositions, and at the other extreme, by derangements, consider the following. Given
n and k satisfying n - k - 2, is it possible to list all permutations so that successive
permutations differ in exactly k positions? This is shown to be possible, unless
[Put89] and in [Sav90], where the listing is cyclic. It was shown further in [RS94a] that the
positions (in which successive permutations differ) could be required to be contiguous.
Putnam claims in [Put90] that when k is even (odd) all permutations (even permutations)
can be generated by k-cycles of elements in contiguous positions. (Putnam's k-cycles need
not be of the form (i;
An interesting question arose in connection with a problem on Hamilton cycles in Cayley
graphs (see Section 11.) Is it possible to generate permutations by "doubly adjacent"
transpositions, i.e., so that successive transpositions are of neighboring pairs? Pair
is considered to be a neighbor of (i
The Johnson-Trotter scheme satisfies this requirement for n - 3, but not for Such a
listing was shown to be possible by Chris Compton in his Ph.D. thesis [Com90]. It might be
hoped that this could result in a very efficient permutation generation algorithm: it would
become unnecessary to decide which of the adjacent pairs to transpose, only whether
the next transposition is to the left or right of the current one. However, in its current form,
Compton's algorithm is not practical, and is quite complex, even with the simplifications
in [CW93].
The problem of generating all permutations of a multiset by adjacent interchanges was
introduced by Lehmer as the Motel Problem [Leh65]. He shows that, because of parity
problems, this is not always possible. It becomes possible, however, if the interchanged
elements are not required to be adjacent and Ko and Ruskey give a CAT algorithm to
generate multiset permutations according to this criterion [KR92].
4 Subsets, Combinations, and Compositions
Since there is a bijection between the subsets of an n-element set (an n-set) and the n-bit
binary numbers, any binary Gray code defines a Gray code for subsets: two binary numbers
differing in one bit correspond to two subsets differing by the addition or deletion of one
element.
For the subclass of combinations ( k-subsets of an n-set for fixed k), several Gray codes
have been surveyed in [Wil89]. As observed in [BER76], a Gray code for combinations
can be extracted from the binary reflected Gray code for n-bit numbers: delete from the
binary reflected Gray code list all those elements corresponding to subsets which do not
have exactly k elements. That which remains is a list of all k-subsets in which successive
sets differ in exactly one element (see Figure 6(a) and compare to Figure 1(a)). The same
list is generated by the revolving door algorithm in [NW78] and it can be described by a
a. Revolving Door b. Strong Minimal Change c. Adjacent Interchange

Figure

Examples of Gray codes for combinations.
simple recursive expression.
A more stringent requirement is to list all k-sets with the strong minimal change property
[EM84]. That is, if a k-set is represented as a sorted k-tuple of its elements, successive k-sets
differ in only one position (see Figure 6(b)). Eades and McKay have shown that such a
listing is always possible. An earlier solution was reported by Chase in [Cha70].
Perhaps the most restrictive Gray code which has been proposed for combinations is to
generate k-subsets of an n-set so that successive sets differ in exactly one element and this
element has either increased or decreased by one. This is called the adjacent interchange
property since if the sets are represented as binary n-tuples, successive n-tuples may differ
only by the interchange of a 1 and a 0 in adjacent positions (see Figure 6(c)). However, this
is not always possible: it was shown that k-subsets of an n-set can be generated by adjacent
interchanges if (i) k=0, 1, n, or is even and k is odd. In all other cases, parity
problems prevent adjacent interchange generation [BW84, EHR84, HR88, Rus88a]. It was
shown by Chase [Cha89] and by a simpler construction in [Rus93] that combinations can
be generated so that successive elements differ either by an adjacent transposition or by the
transposition of two bits that have a single '0' bit between them.
There are several open problems about paths between levels of the Hasse diagram of
the Boolean lattice, B n . The most notorious is the middle two levels problem which is
attributed in [KT88] to Dejter, Erd-os, and Trotter and by others to H'avel and Kelley.
The middle two levels of B 2k+1 have the same number of elements and induce a bipartite,
vertex transitive graph on the k- and k + 1- element subsets of [2k 1]. The question is
whether there is a Hamilton cycle in the middle two levels of B 2k+1 . At first glance, it
would appear that one could take a Gray code listing of the k-subsets, in which successive
elements differ in one element, and, by taking unions of successive elements, create a list
of 1-subsets. Alternating between the lists would give a walk in the middle two levels
graph, but, unfortunately, not a Hamilton path, at least not for any known Gray code on
k-subsets.
The graph formed by the middle two levels is a connected, undirected, vertex-transitive
graph. Thus, either it has a Hamilton path, or it provides a counterexample to the Lov'asz
conjecture. One approach to this problem which has been considered is to try to form a
Hamilton cycle as the union of two edge-disjoint matchings. In [DSW88], it was shown
that a Hamilton cycle in the middle two levels cannot be the union of two lexicographic
matchings. However, other matchings may work and new matchings in the middle two
levels have been defined [KT88, DKS94].
The largest value of k for which a Hamilton cycle is known to exist is

Figure

7 for an example when 3. This unpublished work was done by Moews and
Reid using a computer search [MR]. To speed up the search, they used a necklace-based
approach, gambling that there would be a Hamilton path through necklaces which could
be lifted to a Hamilton cycle in the original graph. We feel that a focus on the middle two
levels of the necklace poset, as described in Section 8, is a promising approach to the middle
two levels problem.
Is there at least a good lower bound on the length of a longest cycle in the middle two
levels of the Boolean lattice? Since this graph is vertex-transitive, a result of Babai [Bab79]
shows that there is a cycle of length at least (3N(k)) 1=2 , where N(k) is the total number of
vertices in the middle two levels of B 2k+1 . A result of Dejter and Quintana gives a cycle of
length
This was improved in [Sav93] to
Figure

7: A Hamilton cycle in the middle two levels of B 7 .
In a welcome breakthrough, Felsner and Trotter showed the existence of cycles of
length at least 0:25N(k) [FT95]. The monotone Gray code, described in Section 1, contains
as a subpath, a path in the middle two levels of length at least 0:5N(k) [SW95]. In [SW95],
this was strengthened to get 'nearly Hamilton' cycles in the following sense: for every ffl ? 0,
there is an h - 1 so that if a Hamilton cycle exists in the middle two levels of B 2k+1 for
h, then there is a cycle of length at least (1 \Gamma ffl)N (k) in the mid-levels of B 2k+1 for
all k - 1. Since Hamilton cycles are known for 1 - k - 11, the construction guarantees a
cycle of length at least 0:839N(k) in the middle two levels of B 2k+1 for all k - 1.
A variation on this problem is the antipodal layers problem: for which values of k is
there a Hamilton path among the k-sets and sets of ng for all n, where two
sets are joined by an edge if and only if one is a subset of the other? Results for limited
values of k and n are given in [Hur94] and [Sim].
A composition of n into k parts is a sequence nonnegative integers whose
sum is n. This is traditionally viewed as a placement of n balls into k boxes. Nijenhuis and
asked in the first edition of [NW78] (p. 292, problem 34) whether it was possible to
a. P (7;

Figure

8: Gray codes for various families of integer partitions
generate the k-compositions of n so that each is obtained from its predecessor by moving
one ball from its box to another. Knuth solved this in 1974 while reading the galleys of the
book and in [Kli82], Klingsberg gives a CAT implementation of Knuth's Gray code.
Combinations and compositions can be simultaneously generalized as follows. Let
denote the set of all ordered t-tuples
t. If m i - s for is the set of
s-combinations of a t-element set. If X is the multiset consisting of m i copies of element
is the collection of s-element submultisets, or s-
combinations of X . In [Ehr73], Ehrlich provides a loopless algorithm to generate multiset
combinations so that successive elements differ in only two positions, but not necessarily
by just \Sigma1 in those positions. It is shown in [RS95] that a Gray code still exists when
the two position can change by only \Sigma1, thereby generalizing Gray code results for both
combinations and compositions.
5 Integer Partitions
A partition of an integer n is a sequence of positive integers x 1
satisfying Algorithms for generating integer partitions in standard
orders such as lexicographic and antilexicographic were presented in [FL80] and [NW78].
The performance of the algorithms in [FL80] is analyzed in [FL81].
An integer partition in standard representation, can also be written
as a list of pairs (y are the distinct integers appearing in the
sequence -, and m i is the number of times y i appears in -. Ruskey notes in [Rus95] that a
lexicographic listing of partitions in this ordered pairs representation has the property that
successive elements of the list differ at most in the last three ordered pairs.
asked the following question regarding a Gray code for integer partitions in the
standard representation there a way to list the partitions of
an integer n in such a way that consecutive partitions on the list differ only in that one part
has increased by 1 and one part has decreased by 1? may decrease to 0
or a 'part' of size 0 may increase to 1.) Yoshimura demonstrated that this was possible for
integers In [Sav89], it is shown constructively to be possible for all n.
The result is a bit more general: for all n - k - 1, there is a way to list the set P (n; k), of
all partitions of n into integers of size at most k, in Gray code order. Unless (n;
the Gray code is max-min. As a consequence, each of the following can also be listed in
Gray code order for all n, partitions of n whose largest part
is k, (2) all partitions of n into k or fewer parts, and (3) all partitions of n into exactly k
parts. See Figure 8(a) for a Gray code listing of P(7; 6). Exponents in the figure indicate
the number of multiple copies.
The approach in [Sav89], was to decompose the partitions problem, P (n; k), into sub-problems
of two forms, a 'P ' form, which was the same form as the original problem, and
a new 'M ' form. It was then shown that the P and M forms could be recursively defined
in terms of (smaller versions of) both forms, thereby yielding a doubly recursive construction
of the partitions Gray code. The algorithm has been implemented [Bee90] and can be
modified to run in time O(jP (n; k)j).
This strategy has been applied to yield Gray codes for other families of integer partitions.
be the set of all partitions of n into parts of size at most k, in which the parts
are required to be congruent to 1 modulo ffi . When just P (n; k). When
2, the elements of P ffi (n; are the partitions of n into odd parts of size at most k. It
is shown in [RSW95] that P ffi (n; can be listed so that between successive partitions, one
part increases by ffi (or ffi ones may appear) and another part decreases by ffi (or ffi ones may
disappear.) (See Figure 8(b).) The Gray code is max-min unless (n;
where a max-min Gray code is impossible.
For the case of D(n; k), the set of partitions of n into odd parts of size at most k, the
same strategy can be applied, but the construction becomes more complex. Surprisingly, it
is still possible to list D(n; in Gray code order: between successive partitions one part
increases by two and one part decreases by two [RSW95]. (See Figure 8(c).) The Gray
code is max-min unless (n; or (12; 6), in which cases a max-min Gray code is
impossible. One observation that follows from this work is that although there are bijections
between the sets of partitions of n into odd parts and partitions of n into distinct parts, no
bijection can preserve such Gray codes.
The same techniques can be used to investigate Gray codes in other families of integer
partitions, but each family has its own quirks: a small number of cases must be handled
specially and subsets needed for linking recursively listed pieces can become empty. Never-
theless, we conjecture that each of the following families has a Gray code enumeration, for
arbitrary values of the parameters n, partitions of n into (a) distinct
odd parts, (b) distinct parts congruent to 1 modulo ffi , (c) at most t copies of each part,
(d) parts congruent to 1 modulo ffi , at most t copies of each part, and (e) exactly d distinct
parts.
6 Set Partitions and Restricted Growth Functions
A set partition is a decomposition of ng into a disjoint union of nonempty subsets
called blocks. Let S(n) denote the set of all partitions of ng. For example, S(4) is
shown in Figure 9(a). The restricted growth functions (RG functions) of length n, denoted
R(n), are those strings a of non-negative integers satisfying a
There is a well-known bijection between S(n) and R(n). For - 2 S(n), order the blocks
of - according to their smallest element, for example, the blocks of
would be ordered f1; 2; 7g, f3; 5; 6; 8g, f4; 10; 11g, f9g. Label
the blocks of - in order by 0; :. The bijection assigns to - the string a
(a)S(4) (b)L(4) in (c) Knuth's (d) modified (e)Ehrlich's
lexicographic Gray code Knuth algorithm
order

Figure

9: Listings of S(4) and R(4).
is the label of the block containing i. The associated string for -
above is 2. For 4, the bijection is illustrated in the first two columns
of

Figure

9.
In [Kay76], Kaye gives a CAT implementation of a Gray code for S(n), attributed to
Knuth in [Wil89]. This was another problem posed by Nijenhuis and Wilf in their book
[NW78] (p. 292, problem 25) and solved by Knuth while reading the galleys. In this Gray
code, successive set partitions differ only in that one element moved to an adjacent block

Figure

9(c).) However, the associated RG functions may differ in many positions. Ruskey
[Rus95] describes a modification of Knuth's algorithm in which one element moves to a block
at most two away between successive partitions and the associated RG functions differ only
in one position by at most two (Figure 9(d).)
Call a Gray code for RG functions strict if successive elements differ in only one position
and in that position by only \Sigma1. Strict Gray codes for R(n) were considered in an early
paper of Ehrlich where it was shown that for infinitely many values of n, they do not exist
[Ehr73]. Nevertheless, Ehrlich was able to find an efficient listing algorithm for R(n) (loop-
free) which has the following interesting property: successive elements differ in one position
and the element in that position can change by 1, or, if it is the largest element in the string,
it can change to 0. Conversely, a 0 can change to a the the largest value v in the string or
to v + 1. For example,
conversely. In the associated list of set partitions, this change corresponds to moving one
element to an adjacent block in the partition, where the first and last blocks are considered
adjacent (Figure 9(e).)
Ehrlich's results are generalized in [RS94b] to the set of restricted growth tails, T (n; k),
which are strings of non-negative integers satisfying a 1 - k and a i - 1+maxfa
1g. (These are a variation of the T (n; m) used in [Wil85] for ranking and unranking set
partitions.) Note that T (n; R(n). Because of parity problems, for all k there are
infinitely many values of n for which T (n; has no strict Gray code, that is, one in which
only one position changes by 1. However, Gray codes satisfying Ehrlich's relaxed criterion
are constructed and they can be made cyclic or max-min, properties not possessed by the
earlier Gray codes.
Consider now set partitions into a fixed number of blocks. For
(n) be the set of partitions of ng into exactly b blocks. The bijection between
S(n) and R(n) restricts to a bijection between S b (n) and
The Ehrlich paper presents a loop-free algorithm for generating S b (n) in which successive
partitions differ only in that two elements have moved to different blocks [Ehr73]. Ruskey
describes a Gray code for R b (n) (and a CAT implementation) in which successive elements
differ in only one position, but possibly by more than 1 in that position [Rus93]. It is shown
in [RS94b] that in general, R b (n) does not have a strict Gray code, even under the relaxed
criterion of Ehlich.
It remains open whether there are strict Gray codes for R(n) and T (n; when the
parity difference is 0.
7 Catalan Families
In several families of combinatorial objects, the size is counted by the Catalan numbers,
defined for n - 0 by
These include binary trees on n vertices [SW86], well-formed sequences of 2n parentheses
[SW86], and triangulations of a labeled convex polygon with
bijections are known between most members of the Catalan family, a Gray code for one
member of the family gives implicitly a listing scheme for every other member of the family.
However, the resulting lists may not look like Gray codes, since bijections need not preserve
minimal changes between elements.
The problem of generating all binary trees with a given number of nodes was considered
in several early papers, including [RH77], [Zak80], and [Zer85]. However, Gray codes in
the Catalan family were first considered in [PR85], where binary trees were represented as
strings of balanced parentheses. It was shown in [PR85] that strings of balanced parentheses
could be listed so that consecutive strings differ only by the interchange of one left and one
right parenthesis. For example '(()())(())' could follow `(()(())())'. The same problem
was considered in [RP90] with the additional restriction that only adjacent left and right
parentheses could be interchanged. For example, now '(()())(())' could not follow `(()(())())',
but could follow '((()))(())'. The result of [RP90] is that all balanced strings of n pairs of
parentheses can be generated by adjacent interchanges if and only if n is even or n ! 5,
and for these cases, a CAT algorithm is given.
A different minimal change criterion, focusing on binary trees, was considered in [Luc87]
and [LRR93]: list all binary trees on n nodes so that consecutive trees differ only by a left
or right rotation at a single node. The rotation operation is common in data structures
where it is used to restructure binary search trees, while preserving the ordering properties.
It was shown that such a Gray code is always possible and it can be generated efficiently
[LRR93]. With a more intricate construction, Lucas was able to show that the associated
graph was hamiltonian [Luc87], giving a cyclic Gray code.
It so happens that under a particular bijection between binary trees with n nodes and
the set of all triangulations of a labeled convex polygon with vertices, rotation in a
binary tree corresponds to the flip of a diagonal in the triangulation [STT88]. So, the results
of [Luc87, LRR93] also give a listing of all triangulations of a polygon so that successive
triangulations differ only by the flip of a single diagonal.
8 Necklaces and Variations
An n-bead, k-color necklace is an equivalence class of k-ary n-tuples under rotation. Figure
lists the lexicographically smallest representatives of the n-bead, k-color necklaces
for (n; asked if it is possible to generate necklaces effi-
ciently, possibly in constant time per necklace. A proposed solution, the FKM algorithm
of Fredricksen, Kessler, and Maiorana, had no proven upper bound better than O(nk n )
[FK86, FM78]. In [WS90] a new algorithm was presented with time complexity O(nN n
where N n
k is the number of n-bead necklaces in k colors. Subsequently, a tight analysis of
the original FKM algorithm showed that it could, in fact, be implemented to run in time
O(N n
giving an optimal solution [RSW92].
Neither of the algorithms above gives a Gray code for necklaces. Can representatives of
all binary n-bead necklaces be listed so that successive strings differ only in one bit position
(as in

Figure

10)? A parity argument shows that this is impossible for even n, but for odd
n the question remains open. However, in the case of necklaces with a fixed number of 1's,
Wang showed, with a very intricate construction, how to construct a Gray code in which
successive necklace representatives differ only by the swap of a 0 and a 1 [Wan94, WS94]

Figure

11.)
It remains open whether necklaces with a fixed number of 1's can be generated in
constant amortized time, either by a modification the FKM algorithm, by a Gray code, or
by any other method.
The Gray code adjacency criterion can be generalized to necklaces with k - 2 beads
by requiring that successive necklaces differ in exactly one position and in that position by
only 1. We conjecture that this can be done if and only if nk is odd. (Parity problems
a. 5-bead binary b. 7-bead binary c. 3-bead ternary

Figure

10: Examples of Gray codes for necklaces.
prevent a Gray code when nk is even.)
For necklaces of fixed weight, when is it possible to list all n-bead k-color necklaces
of weight w so that successive necklaces differ in exactly two positions, one of which has
increased by one and the other, decreased by one? We know of no counterexamples.
To construct a slightly different set of objects, call two k-ary strings equivalent if one is
a rotation or a reversal of the other. The equivalence classes under this relation are called
bracelets. Lisonek [Lis93] shows how to modify the necklace algorithm of [WS90] to generate
bracelets. We know of no Gray code for bracelets and it is open whether it is possible to
generate bracelets in constant amortized time. When beads have distinct colors, bracelets
are the rosary permutations of [Har71, Rea72].
Define a new relation R on n-bead binary necklaces by xRy if some member of x becomes
a member of y by changing a 0 to a 1 in one bit position. The reflexive transitive closure,
R   is a partial order and the resulting poset is the necklace poset. For k - 0 and
the middle two levels of this poset, consisting of necklaces of density k and k have the
same number of elements. Does the bipartite subgraph induced by the middle two levels
have a Hamilton path? This graph is not vertex-transitive, but it may encapsulate the
"hard part" of the middle two levels problem described in Section 4.
A necktie of n bands in k colors is an equivalence class of k-ary n-tuples under reversal.
7 beads, 4 ones 9 beads, 3 ones 8 beads, 4 ones

Figure

11: Examples of Gray codes for binary necklaces with a fixed number of ones.
If a necktie is identified with the lexicographically smallest element in its equivalence class,
Wang [Wan93] shows that for n - 3, a Gray code exists if and only if either n or k is odd.
For this result, two neckties are adjacent if and only if they differ only in one position and
in that position by \Sigma1 modulo k. Further results on neckties appear in [RW94].
9 Linear Extension of Posets
A partially ordered set (S; -) is a set S together with a binary relation - on S which is
reflexive, transitive, and antisymmetric. A linear extension of a poset is a permutation
of the elements of the poset which is consistent with the partial order, that
is, if x i - x j in the partial order, then i - j. The problem of efficiently generating all
the linear extensions of a poset, in any order, has been studied in [KV83, KS74, VR81].
The area of Gray codes for linear extensions of a poset was introduced by Frank Ruskey in
[Rus88b, PR91] as a setting in which to generalize the study of Gray codes for combinatorial
objects. For example, if the Hasse diagram of the poset consists of two disjoint chains, one
of length m and the other of length n, then there is a one-to-one correspondence between
the linear extensions of the poset and the combinations of m objects chosen from m
If the poset consists of a collection of disjoint chains, the linear extensions correspond to
multiset permutations. Other examples are described in [Rus92].
To study the existence of Gray codes, Ruskey constructs a transposition graph corresponding
to a given poset. The vertices are the linear extensions of the poset, two vertices
being joined by an edge if they differ by a transposition. The resulting graph is bipartite. In
[Rus88b], Ruskey makes the conjecture that whenever the parity difference is at most one,
the graph of the poset has a Hamilton path. The conjecture is shown to be true for some
special cases in [Rus92], including posets whose Hasse diagram consists of disjoint chains
and for series parallel posets in [PR93]. The techniques which have been successful so far
involve cutting and linking together listings for various subposets in rather intricate ways.
In many cases where it is known how to list linear extensions by transpositions, it is
also possible to require adjacent transpositions, although possibly with a more complicated
construction [PR91, RS93, Sta92, Wes93]. It has been shown that if the linear extensions
of a poset Q, with jQj even, can be listed by adjacent transpositions, then so can the linear
extensions of QjP , for any poset P [Sta92], where QjP represents the union of posets P
and Q with the additional relations fp qg.
However, most problems in this area remain open. For example, even if the Hasse
diagram of the poset consists of a single tree, the parity difference may be greater than one.
This makes an inductive approach difficult. If the Hasse diagram consists of two trees, each
with an odd number of vertices, the parity difference will be at most one, but it is unknown
whether the linear extensions can be listed in this case. The problem is also open for posets
whose Hasse diagram is a grid or tableau tilted ninety degrees [Rus].
Calculating the parity difference itself can be difficult and Ruskey [Rus] has several
examples of posets for which the parity difference is unknown. (Some parity differences are
calculated in [KR88].) Recently, Stachowiak has shown that computing the parity difference
is #P-complete [Sta]. Even counting the number of linear extensions of a poset is an open
problem for some specific posets, for example, the Boolean lattice [SK87]. Brightwell and
Winkler have recently shown that the problem of counting the number of linear extensions
of a given poset is #-P complete [BW92]. On the brighter side, Pruesse and Ruskey [PR94]
have found a CAT algorithm for listing linear extensions so that successive extensions differ
by one or two adjacent transpositions and Canfield and Williamson [CW95] have shown
how to make it loop-free.
In [PR93], Pruesse and Ruskey consider antimatroids, of which posets are a special
case. Analogous to the case of linear extensions of a poset, they show that the sets of
an antimatroid can be listed so that successive sets differ by at most two elements. In
particular, this gives a listing of the ideals of a poset so that successive ideals differ only in
one or two elements.
Orientations
For an undirected graph G, an acyclic orientation of G is a function on the edges of G which
assigns a direction (u; v) or (v; u) to each edge uv of G in such a way that the resulting
digraph has no directed cycles. Consider the problem of listing the acyclic orientations of G
so that successive list elements differ only by the orientation of a single edge. It is not hard
to see that when G is a tree with n edges, such a listing corresponds to an n bit binary Gray
code; when G is K n , an acyclic orientation corresponds to a permutation of the vertices and
the Johnson-Trotter Gray code for permutations provides the required listing for acyclic
orientations.
Denote by AO(G) the graph whose vertices are the acyclic orientations of G, two vertices
adjacent if and only if the corresponding orientations differ only in the orientation of a single
edge. The graph AO(G) is bipartite and is connected as long as G is simple. Edelman asked,
whenever the partite sets have the same size, whether AO(G) is hamiltonian. It is shown
in [SSW93] that the answer is yes for several classes of graphs, including trees, odd length
cycles, complete graphs, odd ladder graphs, and chordal graphs. On the other hand, the
parity difference is shown to be more than one for several cases, including cycles of even
length and the complete bipartite graphs K m;n with m; n ? 1 and m or n even. The
problem appears to be difficult and it is even open whether AO(K m;n ) is hamiltonian when
mn is odd. However, the square of AO(G) is hamiltonian for any G [PR95, SZ95, Squ94c],
which means that acyclic orientations can be listed so that successive elements differ in the
orientations of at most two edges.
The problem of counting acyclic orientations is #P-complete [Lin86] and it is an open
question whether there is a CAT algorithm to generate them. The fastest listing algorithm
known, due to Squire [Squ94b], requires O(n) average time per orientation, where n is the
number of vertices of the graph.
The linear extensions and acyclic orientations problems can be simultaneously generalized
as follows. For a simple undirected graph G and a subset R of the edges of G, fix an
acyclic orientation oe R of the edges of R. Let AOR (G) be the subgraph of AO(G) induced by
the acyclic orientations of G which agree with oe R on R. Is this bipartite graph hamiltonian
whenever the parity difference allows?
is the acyclic orientations graph of G. AOR (G) becomes the
linear extensions adjacency graph of an n element poset P when when
and oe R are defined by the covering relations in P . In contrast to the situation for linear
extensions and acyclic orientations, the square of AOR (G) is not necessarily hamiltonian.
Counterexamples appear in [Squ94c] and [PR95].
Cayley Graphs and Permutation Gray Codes
Many Gray code problems for permutations are best discussed in the setting of Cayley
graphs. Given a finite group G and a set X of elements of G, the Cayley graph of G,
C[G; X ], is the undirected graph whose vertices are the elements of G and in which there
is an edge joining u and v if and only if Equivalently,
uv is an edge in G if and only if u \Gamma1 v or v \Gamma1 u is in X . C[G; X ] is always vertex transitive
and is connected if and only if X [X \Gamma1 generates G. It is an open question whether every
Cayley graph is hamiltonian. (There are generating sets for which the Cayley digraph is not
hamiltonian [Ran48].) This is a special case of the more general conjecture of Lov'asz that
every connected, undirected, vertex-transitive graph has a Hamilton path [Lov70]. Results
on Hamilton cycles are surveyed in [Als81] for vertex transitive graphs and in [Gou91] for
general graphs. A survey of Hamilton cycles in Cayley graphs can be found in [WG84] and
in the recent update of Curran and Gallian [CG96]. We focus here on a few recent questions
which arose in the context of Gray codes.
Suppose the group G is S n , the symmetric group of permutations of n symbols, and let
X be a generating set of S n . Then a Hamilton cycle in the Cayley graph C[G; X ] can be
regarded as a Gray code for permutations in which successive permutations differ only by
a generator in X . Even in the special case of G = S n , it is still open whether every Cayley
graph of S n has a Hamilton cycle. One of the most general results on the hamiltonicity of
Cayley graphs for permutations was discovered by Kompel'makher and Liskovets in 1975.
First note that for S n generated by the basis n)g, the Johnson-
Trotter algorithm from Section 3 for generating permutations by adjacent transpositions
gives a Hamilton cycle in C[G; X ]. Kompel'makher and Liskovets generalized this result
to show that if X is any set of transpositions generating S n , then C[S
[KL75]. Independently, and with a much simpler argument, Slater showed that these graphs
have Hamilton paths [Sla78]. Tchuente [Tch82] extended the results of [KL75, Sla78] to
show that the Cayley graph of S n , on any generating set X of transpositions, is not only
hamiltonian, but Hamilton-laceable, that is, for any two vertices u; v of different parity
there is a Hamilton path which starts at u and ends at v.
It is unknown whether any of these results generalize to the case when X is a generating
set of involutions (elements of order 2) for S n . An involution need not be a transposition:
for example the product of disjoint transpositions is an involution. In perhaps the simplest
nontrivial case, when S n is generated by three involutions, it is easy to show that if any two
of the generators commute, then the Cayley graph is hamiltonian. (Cayley graphs arising
in change ringing frequently have this property [Ran48, Whi83].) However if no two of the
three involutions commute, it is open whether the Cayley graph is hamiltonian. As a specific
example, we have not been able to determine whether there is a Gray code for permutations
in which successive permutations may differ only by one of the three operations: (i) exchange
positions 1 and 2, (ii) reverse the sequence, and (iii) reverse positions 2 through n of the
sequence.
Conway, Sloane, and Wilks have a related result on Gray codes for reflection groups: if
G is an irreducible Coxeter group (a group generated by geometric reflections) and if X is
the canonical basis of reflections for the group, then C[G; X ] is hamiltonian [CSW89]. This
result makes use of the fact that in any set of three or more generators from this basis,
there is always some pair of generators which commute (the Coxeter diagram for the basis
is a tree). It is straightforward to show for groups G and H , with generating sets X and Y ,
respectively, that if C[G; X ] and C[H; Y ] are hamiltonian, and at least one of G and H have
even order, then C[G \Theta H; X \Theta Y ] is hamiltonian. As noted in [CSW89], since any reflection
group R is a direct product of irreducible Coxeter groups G 1 \Theta G 2 \Theta
canonical basis for G i , the Cayley graph of R with respect to the basis
is hamiltonian.
This result has an interesting geometric interpretation. We can associate with a finite
reflection group a tessellation of a surface in n-space by a spherical (n \Gamma 1)-simplex. The
spherical simplices of the tesselation correspond to group elements, and the boundary shared
by two simplices corresponds to a reflection in the bounding hyperplane. Thus, a Hamilton
cycle in the Cayley graph corresponds to a traversal of the surface, visiting each simplex
exactly once.
It seems likely that if there do exist non-hamiltonian Cayley graphs of S n , there will
be examples in which the vertices have small degree, such as S n generated by three involutions
as described above. As a candidate counterexample, Wilf suggested the group
of permutations generated by the two cycles (1 2) and (1
and Williamson were able to find a Hamilton cycle in this graph using their Gray code for
generating permutations by doubly adjacent transpositions, described in Section 3 [CW93].
The results of [KL75, Sla78] were generalized in a different way in [RS93]. It was shown
there that when n - 5, for any generating set X of transpositions of S n and for any
transposition permutations in S n can be listed so that successive permutations
differ only by a transposition in X and every other transposition is - . That is, the perfect
matching in C[S defined by - is contained in a Hamilton cycle. One application of this
result is to Cayley graphs for the alternating group, A n , consisting of all even permutations
n. For example, letting n), the result in
[RS93] implies that the Cayley graph of A n with respect to the generating set
is hamiltonian. This result was obtained earlier with a direct
argument by Gould and Roth [GR87].
12 Generalizations of de Bruijn Sequences
A de Bruijn sequence of order n is a circular binary sequence of length 2 n in which every
n-bit number appears as a contiguous subsequence. This provides a Gray code listing of
binary sequences in which successive elements differ by a rotation one position left followed
by a change of the last element. It is known that these sequences exist for all n and the
standard proof shows that a de Bruijn sequence of order n corresponds to an Euler tour in
the de Bruijn digraph whose vertices are the binary n-tuples, with one edge
binary n-tuple x
This result has been generalized for k-ary n-tuples [Fre82], for higher dimensions (de
Bruijn tori) [Coc88, FFMS85], and for k-ary tori [HI95]. It is known also, for any m
satisfying , that there is a cyclic binary sequence of length m in which no n-tuple
appears more than once [Yoe62]. So, the de Bruijn graph contains cycles of all lengths
n. Results on de Bruijn cycles have been applied to random number generation in
information theory [Gol64] and in computer architecture, where the de Bruijn graph is
recognized as a bounded degree derivative of the shuffle-exchange network [ABR90].
Chung, Diaconis, and Graham generalized the notion of a de Bruijn sequence for binary
numbers to universal cycles for other families of combinatorial objects [CDG92]. Universal
cycles for combinations were studied by Hurlbert in [Hur90] and some interesting problems
remain open. A universal cycle of order n for permutations is a circular sequence x
of length of symbols from Mg in which every permutation
is order isomorphic to some contiguous subsequence x
means that for 1 - As an example, the sequence
123415342154213541352435 is a universal cycle of order 4 with 5. In [CDG92], the
goal is to choose M as small as possible to guarantee the existence of a universal cycle.
It is clear that M must satisfy 2. It is conjectured in [CDG92] that
although the best upper bound they were able to obtain was
sufficient.
As another approach, we can relax the constraint on the length of the sequence, while
requiring for the shortest circular sequence of symbols from ng
which contains every permutation as a contiguous subsequence at least once. Jacobson and
West have a simple construction for such a sequence of length 2n! [JW].
Concluding Remarks
This paper has included a sampling of Gray code results in several areas, particularly those
which have appeared since the survey of Wilf [Wil89], in which many of these problems
were posed. Good references for early work on Gray codes are [Ehr73] and [NW78]. For
a comprehensive treatment of Gray codes and other topics in combinatorial generation, we
look forward to the book in preparation by Ruskey [Rus95]. Additional information on
Gray codes also appears in the survey of Squire [Squ94a]. In [Gol93], Goldberg considers
generating combinatorial structures for which achieving even polynomial delay is hard. For
surveys on related material, see [Als81] for long cycles in vertex transitive graphs, [Gou91]
for hamiltonian cycles, [WG84] and the recent update [CG96] for Cayley graphs, and [Sed77]
for permutations.

Acknowledgements

I am grateful to Herb Wilf for collecting and sharing such an intriguing
array of 'Gray code' problems. His work, as well as his enthusiasm, has been inspiring.
I would also like to thank Frank Ruskey, my frequent co-author, for many provoking dis-
cussions, and for his constant supply of interesting problems. Both have provided helpful
comments on earlier versions on this manuscript. For additional comments and suggestions,
I am grateful to Donald Knuth and to an anonymous referee.



--R

Group action graphs and parallel architectures.
The search for long paths and cycles in vertex-transitive graphs and digraphs
A data structure based on Gray code encoding for graphics and image processing.
Long cycles in vertex-transitive graphs
Implementation of an algorithm to list Gray code sequences of partitions.
Efficient generation of the binary reflected Gray code.
Algorithm 6.
Permutation of the elements of a vector (Algorithm 29) and Fast permutation of the elements of a vector (Algorithm 30).
Balanced Gray codes.
Gray codes with restricted density.
Counting linear extensions is
Symbolic Gray codes as a data allocation scheme for two disc systems.
Universal cycles for combinatorial structures.
Hamiltonian cycles and paths in Cayley graphs and digraphs - a survey
Algorithm 382: Combinations of M out of N objects.
Combination generation and Graylex ordering.
Toroidal tilings from de Bruijn-good cyclic sequences
Hamilton cycles in the Cayley graph of Sn and a doubly adjacent Gray code.
Subcube allocation and task migration in hypercube machines.
Gray codes for reflection groups.
Hamilton circuits in tree graphs.
Doubly adjacent Gray codes for the Symmetric group: how to braid n strands.

A combinatorial problem.
Gray codes for randomization procedures.
An explicit 1-factorization in the middle of the Boolean lattice
Long cycles in revolving door graphs.
Lexicographic matchings cannot form hamiltonian cycles.
Loopless algorithms for generating permutations
Some Hamilton paths and a minimal change algorithm.
An algorithm for generating subsets of fixed size with a strong minimal change property.
Problem 1186: Solution I.
Gray codes for partial match and range queries.
On de Bruijn arrays.
An algorithm for generating necklaces of beads in two colors.
A binary tree representation and related algorithms for generating integer partitions.
An analysis of two related loop-free algorithms for generating integer partitions
Necklaces of beads in k colors and k-ary de Bruijn sequences
The shuffle-exchange network has a hamiltonian path
Observations on the complexity of generating quasi-gray codes
A survey of full length nonlinear shift register cycle algorithms.
Colorings of diagrams of interval orders and ff-sequences
Curious properties of the Gray code and how it can be used to solve puzzles.
Personal communication.
Gray codes and paths on the n-cube
Computers and Intractability
Gray codes with optimized run lengths.
Digital Communications with Space Applications.
Efficient Algorithms for Listing Combinatorial Structures.
Updating the hamiltonian problem - a survey
Cayley digraphs and (1
Pulse code communications.
Generation of rosary permutations expressed in hamiltonian circuits.
Permutations by interchanges.
Origins on the binary code.
On the tree graph of a matroid.
On the de Bruijn torus problem.
An efficient implementation of the Eades
Universal Cycles: On Beyond de Bruijn.
The antipodal layers problem.
Hamilton cycles in regular 2-connected graphs
Generation of permutations by adjacent transpositions.
Personal communication.
Combinatorial Gray codes.
A Gray code for set partitions.
Sequential generation of arrangements by means of a basis of transpositions.
A Gray code for compositions.
Solution of some multi-dimensional lattice path parity difference recurrence relations
Generating permutations of a bag by interchanges.
A structured program to generate all topological sorting arrangements.
Explicit matchings in the middle levels of the Boolean lattice.
On the generation of all topological sortings.
The machine tools of combinatorics.
Permutation by adjacent interchanges.
Hard enumeration problems in geometry and combinatorics.
Generating bracelets
A Gray code based ordering for documents on shelves: Classificaton for browsing and retrieval.
Problem 11.

A technique for generating Gray codes.
The rotation graph of binary trees is hamiltonian.
Gray code generation for MPSK signals.
A problem in arrangements.
Problem 1186.
Electronic mail communication (via J.
Combinatorial Algorithms for Computers and Calculators.
Binary tree Gray codes.
Generating the linear extensions of certain posets by adjacent transpositions.
Gray codes from antimatroids.
Generating linear extensions fast.
The prism of the acyclic orientation graph is hamiltonian.
A Gray code variant: sequencing permutations via fixed points.
Combinatorial Gray code and a generalization of the Johnson- Trotter algorithm to contiguous k-cycles
Problem 1186.
A new method of generating Hamilton cycles on the n-cube
A campanological problem in group theory.
Counting sequences.
Note on the generation of rosary permutations.
Generating binary trees lexicographically.
Data compression and Gray-code sorting
Generating binary trees by transpositions.
Generating all permutations by graphical derangements.
Hamilton cycles which extend transposition matchings in Cayley graphs of Sn

Gray codes for set partitions and restricted growth tails.
A Gray code for combinations of a multiset.
Generating necklaces.
Gray code enumeration of families of integer partitions.
private communication.
Adjacent interchange generation of combinations.
Research problem 90.
Generating linear extensions of posets by transpositions.
Simple combinatorial Gray codes constructed by reversing sublists.
Combinatorial Generation.
Generating neckties: algorithms
Gray code sequences of partitions.
Generating permutations with k-differences
Long cycles in the middle two levels of the Boolean lattice.
Permutation generation methods.
Hamiltonian bipartite graphs.
The number of linear extensions of subset ordering.
Generating all permutations by graphical transpositions.
Combinatorial Gray codes and efficient generation.
Generating the acyclic orientations of a graph.
Two new Gray codes for acyclic orientations.
Gray codes for A-free strings
Gray code results for acyclic orientations.
Finding parity difference by involutions.
Hamilton paths in graphs of linear extensions for unions of posets.
Rotation distance
Constructive Combinatorics.
Monotone Gray codes and the middle two levels problem.
A note on the connectivity of acyclic orientations graphs
Generation of permutations by graphical exchanges.

An algorithm to generate all topological sorting arrangements.
A technique for generating specialized Gray codes.
A note on Gray codes for neckties
A Gray Code for Necklaces of Fixed Density.
Generation of permutations by transposition.
Generating linear extensions by adjacent transpositions.
A survey - hamiltonian cycles in Cayley graphs
Ringing the changes.
Combinatorics for Computer Science.
Generalized Gray codes.
Combinatorial Algorithms: An Update.
A new algorithm for generating necklaces.
Gray codes for necklaces of fixed density
Construction of uniform Gray codes.
Binary ring sequences.
Ranking and unranking algorithms for trees and other combinatorial ob- jects
Lexicographic generation of ordered trees.
Generating binary trees using rotations.
--TR

--CTR
Elizabeth L. Wilmer , Michael D. Ernst, Graphs induced by Gray codes, Discrete Mathematics, v.257 n.2-3, p.585-598, 28 November
Colin Murray , Carsten Friedrich, Visualisation of satisfiability using the logic engine, proceedings of the 2005 Asia-Pacific symposium on Information visualisation, p.147-152, January 01, 2005, Sydney, Australia
Khaled A. S. Abdel-Ghaffar, Maximum number of edges joining vertices on a cube, Information Processing Letters, v.87 n.2, p.95-99, 31 July
Tadao Takaoka , Stephen Violich, Combinatorial generation by fusing loopless algorithms, Proceedings of the 12th Computing: The Australasian Theroy Symposium, p.69-77, January 16-19, 2006, Hobart, Australia
V. V. Kuliamin, Test Sequence Construction Using Minimum Information on the Tested System, Programming and Computing Software, v.31 n.6, p.301-309, November  2005
Vincent Vajnovszki, A loopless algorithm for generating the permutations of a multiset, Theoretical Computer Science, v.307 n.2, p.415-431, 7 October
James Korsh , Paul Lafollette, A loopless Gray code for rooted trees, ACM Transactions on Algorithms (TALG), v.2 n.2, p.135-152, April 2006
Gerard J. Chang , Sen-Peng Eu , Chung-Heng Yeh, On the (n,t)-antipodal Gray codes, Theoretical Computer Science, v.374 n.1-3, p.82-90, April, 2007
Kenneth A. Ross, Selection conditions in main memory, ACM Transactions on Database Systems (TODS), v.29 n.1, p.132-161, March 2004
Jean Pallo, Generating binary trees by Glivenko classes on Tamari lattices, Information Processing Letters, v.85 n.5, p.235-238, March
cayley graphs;hamilton cycles;permutations;combinations;linear extensions;vertex-transitive graphs;de Bruijn sequences;boolean lattice;set partitions;acyclic orientations;gray codes;restricted growth functions;catalan families;integer partitions;necklaces;compositions;binary strings