One Sequence to Rule them All

Prangya Parida, University of Ottawa

A binary reflected Gray code (BRGC), denoted by B(n), is an ordering of the 2n binary n-tuples such that any two consecutive tuples differ in exactly one bit. This object can also be generated using a greedy approach (introduced by Williams): start the list with the zero n-tuple and then repeatedly create a new tuple by flipping the rightmost possible bit. It is also well known that the position of the bit that changes at each step in the generation of B(n) is given by the ruler sequence (OEIS A001511). This observation further leads to a loopless generation of B(n) (due to Bitner, Ehrlich, and Reingold), where each successive tuple can be obtained in O(1) time.

Mixed-radix reflected Gray codes and mixed-radix modular Gray codes are natural extensions of the BRGC, where the base of each position is not necessarily binary. They are extensively discussed in The Art of Computer Programming, Volume 4A by Knuth; their respective loopless algorithms can be found as Algorithm H and Exercise 77 in Section 7.2.1.1.

In this talk, we discuss that both of these Gray codes built on a mixed-radix base are guided by the same change sequence, which allows them to be generated in parallel. We show that modular Gray codes can also be generated using a greedy cyclic increment approach, generalizing the greedy method for generating the BRGC. Furthermore, we present a new family of modular Gray codes that can be constructed starting from any tuple w, and then generating the next word using the greedy cyclic increment approach that is lexicographically greater than or equal to w. We show that although this order is not a suffix of the full modular Gray code, its change sequence is a suffix of the change sequence of the full modular Gray code for the given base.

This is joint work with Lucia Moura, Brett Stevens, and Aaron Williams.