Linear time construction of a compressed Gray code (Q1761499)

A (cyclic) Gray code for the set \(\{0,1\}^n \) is a (cyclic) ordering of all binary strings of length \(n\) such that the Hamming distance (number of positions that are different) between any two consecutive strings is exactly one. The authors present a cyclic Gray code \(C_n\) whose graph of transitions is isomorphic to an induced subgraph of the \(d\)-dimensional hypercube, where \(d=\lceil \log n\rceil\). As a consequence, \(C_n\) can be represented so that only \({\mathcal O}(\log \log n)\) bits per \(n\)-length binary string are needed. Finally, they give a generating algorithm for the transition sequences of \(C_n\) in linear time with respect to the output size.