Loopless Gray code enumeration and the Tower of Bucharest
Open accessAbstract
We give new algorithms for generating all n-tuples over an alphabet of m letters, changing only one letter at a time (Gray codes). These algorithms are based on the connection with variations of the Tower of Hanoi game. Our algorithms are loopless, in the sense that the next change can be determined in a constant number of steps, and they can be implemented in hardware. We also give another family of loopless algorithms that is based on the idea of working ahead and saving the work in a buffer.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Gray codes exist for non-binary encodings.
“Gray codes also exist for non-binary encodings43.”
From Laser writing in glass for dense, fast and efficient archival data storage (2026) · cites this paper as [43]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,097 · see citing works
On generating all maximal independent sets
Johnson, D. S., Yannakakis, M., & Papadimitriou, C. H. (1988) · Information Processing Letters · doi:10.1016/0020-0190(88)90065-8 · Cited by 780 · see citing works
Purely Functional Data Structures
Okasaki, C. (1998) · Cambridge University Press eBooks · doi:10.1017/cbo9780511530104 · Cited by 635 · see citing works
The Design of Dynamic Data Structures
(1983) · Springer eBooks · doi:10.1007/bfb0014927 · Cited by 321 · see citing works
Efficient generation of the binary reflected gray code and its applications
Bitner, J. R., Ehrlich, G., & Reingold, E. M. (1976) · Communications of the ACM · doi:10.1145/360336.360343 · Cited by 240 · see citing works
Ehrlich, G. (1973) · Journal of the ACM · doi:10.1145/321765.321781 · Cited by 186 · see citing works
A new representation for linear lists
Guibas, L. J., McCreight, E. M., Plass, M. F., et al. (1977) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800105.803395 · Cited by 151 · see citing works
Real-time queue operations in pure LISP
Hood, R. T., & Melville, R. (1981) · Information Processing Letters · doi:10.1016/0020-0190(81)90030-2 · Cited by 98 · see citing works
Buneman, P., & Levy, L. S. (1980) · Information Processing Letters · doi:10.1016/0020-0190(80)90150-7 · Cited by 74 · see citing works
The Tower of Hanoi – Myths and Maths
Hinz, A., Klavžar, S., Milutinović, U., et al. (2013) · Springer eBooks · doi:10.1007/978-3-0348-0237-6 · Cited by 70 · see citing works
The Tower of Hanoi--myths and maths
(2013) · Choice Reviews Online · doi:10.5860/choice.51-1544 · Cited by 69 · see citing works
Simple and efficient purely functional queues and deques
Okasaki, C. (1995) · Journal of Functional Programming · doi:10.1017/s0956796800001489 · Cited by 65 · see citing works
Gardner, M. R. (1972) · Scientific American · doi:10.1038/scientificamerican0872-106 · Cited by 65 · see citing works
Scorer, R. S., Grundy, P. M., & Smith, C. A. B. (1944) · The Mathematical Gazette · doi:10.2307/3606393 · Cited by 56 · see citing works
Proceedings of the ninth annual ACM symposium on Theory of computing
Hopcroft, J. E., Friedman, E. P., & Harrison, M. A. (1977) · Cited by 37 · see citing works
The Tower of Hanoi with Forbidden Moves
Sapir, A. (2004) · The Computer Journal · doi:10.1093/comjnl/47.1.20 · Cited by 27 · see citing works
Counting and Enumerating Crossing-free Geometric Graphs
Wettstein, M. (2014) · doi:10.1145/2582112.2582145 · Cited by 15 · see citing works
Misra, J. (1975) · ACM Transactions on Mathematical Software · doi:10.1145/355644.356449 · Cited by 14 · see citing works
A constant-time algorithm for middle levels Gray codes
Mütze, T., & Nummenpalo, J. (2017) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974782.147 · Cited by 14 · see citing works
Proceedings of the 6th international conference on Fun with Algorithms
Kranakis, E., Kriz̧anc, D., & Luccio, F. L. (2012) · Cited by 10 · see citing works
Kosaraju, S. R., & Pop, M. (1998) · Lecture notes in computer science · doi:10.1007/3-540-68535-9_4 · Cited by 8 · see citing works
Loopless Gray Code Enumeration and the Tower of Bucharest
Herter, F., & Rote, G. (2016) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.fun.2016.19 · Cited by 3 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Laser writing in glass for dense, fast and efficient archival data storage
Microsoft Research Project Silica Team, Allison, J., Anderson, P., Aranas, E., Assaf, Y., Black, R., Caballero, M., Canakci, B., Chattaway, J. A., Chatzieleftheriou, A., et al. (2026) · Nature · doi:10.1038/s41586-025-10042-w · Cited by 25 · see citing works
- Authors
- Herter, F., & Rote, G.
- Affiliations
- Freie Universität Berlin (DE)
- Corresponding author
- Rote, Günter
- ORCID
- Rote, Günter
- Venue
- Theoretical Computer Science
- Publisher
- Elsevier BV
- Published
- 2018-11
- Volume
- 748
- Pages
- 40-54
- ISSN
- 0304-3975 (ISSN-L)
- OpenAlex
- W2343738579
- Cited by
- 9
- References
- 22
- Citations by year
- 2026: 1 · 2025: 2 · 2023: 2 · 2020: 1 · 2019: 1 · 2017: 2
- FWCI
- 1.74
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- www.elsevier.com/tdm/userlicense/1.0/ (tdm)
- www.elsevier.com/legal/tdmrep-license (tdm)
- www.elsevier.com/open-access/userlicense/1.0/ (vor, 1474 d)
- doi.org/10.15223/policy-017 (stm-asf)
- doi.org/10.15223/policy-037 (stm-asf)
- doi.org/10.15223/policy-012 (stm-asf)
- doi.org/10.15223/policy-029 (stm-asf)
- doi.org/10.15223/policy-004 (stm-asf)
- Locations
- Theoretical Computer Science (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) (submittedVersion, cc-by)
- arXiv (Cornell University)
- Leibniz international proceedings in informatics (cc-by)
- Fun with Algorithms
- Topics
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Advanced Combinatorial Mathematics
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Keywords
- Gray code, Tower of Hanoi, hardware implementation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
