Document Open Access Logo

Loopless Gray Code Enumeration and the Tower of Bucharest

Authors Felix Herter, Günter Rote

PDF
Thumbnail PDF

File

LIPIcs.FUN.2016.19.pdf
  • Filesize: 1.08 MB
  • 19 pages

Document Identifiers

Author Details

Felix Herter
Günter Rote

Cite As Get BibTex

Felix Herter and Günter Rote. Loopless Gray Code Enumeration and the Tower of Bucharest. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FUN.2016.19

Abstract

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 Towers 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.

Subject Classification

Keywords
  • Tower of Hanoi
  • Gray code
  • enumeration
  • loopless generation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. James R. Bitner, Gideon Ehrlich, and Edward M. Reingold. Efficient generation of the binary reflected Gray code and its applications. Commun. ACM, 19(9):517-521, 1976. Google Scholar
  2. Peter Buneman and Leon Levy. The towers of Hanoi problem. Information Processing Letters, 10(4-5):243-244, 1980. Google Scholar
  3. Gideon Ehrlich. Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. J. Assoc. Comput. Mach., 20(3):500-513, July 1973. Google Scholar
  4. Martin Gardner. The curious properties of the Gray code and how it can be used to solve puzzles. Sci. American, 227:106-109, 1972. Google Scholar
  5. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics. Addison-Wesley, 1989. Google Scholar
  6. Dah-Jyh Guan. Generalized Gray codes with applications. Proc. Natl. Sci. Council, Republic of China (A), 22(6):841-848, 1998. Google Scholar
  7. Leo J. Guibas, Edward M. McCreight, Michael F. Plass, and Janet R. Roberts. A new representation for linear lists. In Proceedings of the Ninth Annual ACM Symposium on Theory of Computing, STOC'77, pages 49-60, New York, NY, USA, 1977. ACM. Google Scholar
  8. Felix Herter and Günter Rote. Loopless Gray code enumeration and the Tower of Bucharest. Preprint arXiv 1604.06707 [cs.DM], April 2016. Google Scholar
  9. Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr. The Tower of Hanoi - Myths and Maths. Birkhäuser, 2013. Google Scholar
  10. Donald E. Knuth. Combinatorial Algorithms, Part 1, volume 4A of The Art of Computer Programming. Addison-Wesley, 2011. Google Scholar
  11. Jayadev Misra. Remark on Algorithm 246. ACM Trans. Math. Software, 1(3):285, 1975. Google Scholar
  12. Amir Sapir. The towers of Hanoi with forbidden moves. The Computer Journal, 47(1):20-24, 2004. Google Scholar
  13. R. S. Scorer, P. M. Grundy, and C. A. B. Smith. Some binary games. The Mathematical Gazette, 28(280):96-103, 1944. Google Scholar
  14. Manuel Wettstein. Counting and enumerating crossing-free geometric graphs. Preprint arXiv 1604.05350 [cs.CG], April 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact