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.
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 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 (m1,m2,…,mn), whereas the definition in Section 5 of the journal version (3.) uses the reverse order, which is consistent with the order (an,an-1,…,a1) in which the sequence of digits is produced.Last update: November 22, 2018.