1997/01/01 by Carla D. Savage · 7 citations
Mathematics · Engineering · Computer Science · #Advanced Combinatorial Mathematics #graph theory and CDMA systems #Cellular Automata and Applications #Gray code #Gray (unit) #Mathematics #Binary number #Discrete geometry #Combinatorial optimization #Combinatorial algorithms #Combinatorial analysis #Combinatorics #Computer science #Discrete mathematics #Algorithm #Arithmetic
paper · doi:10.1137/s0036144595295272
openalex publication_date 1997/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.