This is based on work done about 20 years ago with a former student Jim McShea.

Gray codes were introduced by Bell Labs physicist Frank Gray in the 1950s. As introduced, a Gray code is an ordering of the n-tuples in such that two successive terms differ in only one position. A Gray code can be regarded as a Hamiltonian path in the cube graph. For example:

[[0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0], [0, 1, 1], [1, 1, 1], [1, 0, 1], [0, 0, 1]]

These can be generalized to n-tuples of integers (mod m) in the obvious way.

Gray codes have several applications:

- solving puzzles such as the Tower of Hanoi and the Brain [G],
- analog-digital-converters (goniometers) [S],
- Hamiltonian circuits in hypercubes [Gil] and Cayley graphs of Coxeter groups [CSW],
- capanology (the study of bell-ringing) [W],
- continuous space-filling curves [Gi],
- classification of Venn diagrams [R],
- design of communication codes,
- and more (see Wikipedia).

Here's a SageMath/Python function for computing Gray codes. def graycode(length,modulus): """ Returns the n-tuple reverse Gray code mod m. EXAMPLES: sage: graycode(2,4) [[0, 0], [1, 0], [2, 0], [3, 0], [3, 1], [2, 1], [1, 1], [0, 1], [0, 2], [1, 2], [2, 2], [3, 2], [3, 3], [2, 3], [1, 3], [0, 3]] """ n,m = length,modulus F = range(m) if n == 1: return [[i] for i in F] L = graycode(n-1, m) M = [] for j in F: M = M+[ll+[j] for ll in L] k = len(M) Mr = [0]*m for i in range(m-1): i1 = i*int(k/m) i2 = (i+1)*int(k/m) Mr[i] = M[i1:i2] Mr[m-1] = M[(m-1)*int(k/m):] for i in range(m): if is_odd(i): Mr[i].reverse() M0 = [] for i in range(m): M0 = M0+Mr[i] return M0

REFERENCES

[CSW] J. Conway, N. Sloane, and A. Wilks, “Gray codes and reflection groups”, Graphs and combinatorics 5(1989)315-325

[E] M. C. Er, “On generating the N-ary reflected Gray codes”, IEEE transactions on computers, 33(1984)739-741

[G] M. Gardner, “The binary Gray code”, in Knotted donuts and other mathematical entertainments, F. H. Freeman and Co., NY, 1986

[Gi] W. Gilbert, “A cube-filling Hilbert curve”, Math Intell 6 (1984)78

[Gil] E. Gilbert, “Gray codes and paths on the n-cube”, Bell System Technical Journal 37 (1958)815-826

[R] F. Ruskey, “A Survey of Venn Diagrams“, Elec. J. of Comb.(1997), and updated versions.

[W] A. White, “Ringing the cosets”, Amer. Math. Monthly 94(1987)721-746

You must be logged in to post a comment.