Felix Herter and Günter Rote:

Loopless Gray code enumeration and the Tower of Bucharest

  1. In: Proceedings of the 8th International Conference on Fun with Algorithms (FUN 2016). La Maddalena, Italy, June 8–10, 2016. Editors: Erik D. Demaine and Fabrizio Grandoni, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2016, Vol. 49, pp. 19:1–19:18. doi:10.4230/LIPIcs.FUN.2016.19.
  2. Preprint arXiv:1604.06707, April 2016. [cs.DM].
  3. Revised and extended version, to appear in Theoretical Computer Science.

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.

The appendix of the conference version (1.) contains, as additional material, prototype simulations of the most important algorithms in the programming language Python. The appendix of the arXiv preprint (2.) contains simulations of all algorithms of the paper. Program source code is contained with the source files of the paper.

  pdf file (gzipped)
other papers about this subject

Note

The reference program from Appendix A.4 of the conference version (1.) and Appendix A.9 of the preprint (2.) for generating the mixed-radix Gray code according to the definition will not work with Python version 3.7 or later. Here is a replacement program:

def mixed_Gray_code(ms):
     "a generator for the mixed-radix Gray code"
     if ms:
         m = ms[0]
         G1 = mixed_Gray_code(ms[1:])
         while True:
           try:
             g = next(G1)
             for lastdigit in range(0,m):
                 yield g+(lastdigit,)
             g = next(G1)
             for lastdigit in reversed(range(0,m)):
                 yield g+(lastdigit,)
           except StopIteration:
             return
     else:
         yield ()
Last update: July 27, 2017.