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. Theoretical Computer Science 748 (2018), 40–54, special issue for FUN'2016. doi:10.1016/j.tcs.2017.11.017

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. The journal version (3.) contains several additional sections that discuss the results in a larger context.

Note on the python programs in the appendix

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:])
         try:
             while True:
                 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 ()

Note that this program expects the sequence ms of radixes in the order (m₁,m₂,…,m_n), whereas the definition in Section 5 of the journal version (3.) uses the reverse order, which is consistent with the order (a_n,a_n-1,…,a₁) in which the sequence of digits is produced.