Dense gray codes in mixed radices
Jessica C. Fan, Thomas H. Cormen · 2017
The standard binary reflected Gray code produces a permutation of the sequence of integers (0, 1,..., n - 1), where n is a power of 2, such that the binary representation of each integer in the permuted sequence differs from the binary representation of the preceding integer in exactly one bit. In an earlier paper, we presented two methods to compute binary dense Gray codes, which extend the possible values of n to the set of all positive integers while preserving both the Gray-code property - only one bit changes between each pair of consecutive integers - and the denseness property - the sequence contains exactly the n integers 0 to n - 1. This paper generalizes our method for binary dense Gray codes to arbitrary radices that may be either a single fixed radix for all digits or mixed radices, so that each digit may have a different radix. That is, we show how to produce a permutation of (0, 1, ..., n-1) represented in any set of radices, such that the representation of each number differs from the representation of the preceding number in exactly one digit, and the values of these digits differ by exactly 1. We provide a simple formula for this permuation, which we can use to quickly compute a Hamiltonian path for a dynamic array of n nodes, where the nodes are added and deleted in order along the k dimensions of a grid network.