Dana Jansens

In order to count from 0 to 2^{d}-1, we require a bit
string of dimension at least *d*. Consider a sequence of bit
strings of dimension *d*, where each string differs from the next in
a constant number of bits, and the same holds for the first and last
strings in the sequence. We call this sequence a cyclic quasi-Gray
code. In order to count using this sequence of bit strings, we must
generate each bit string using the previous string as the input.

We examine the problem of efficiently generating quasi-Gray codes, by considering the number of bits read and written at each generating step, the average number of bits read while generating the entire code, and the number of strings generated in the code. Our results give a trade-off between these four constraints, and present algorithms which do less work on average than previous results, while also increasing the number of strings generated.

First we will examine a novel algorithm for generating sequences
of length 2^{d} using *d* bits, while keeping
the average bits read to O(log *d*). Then we will use this
to build algorithms that lead to a method for generating sequences
of length arbitrarily close to 2^{d} using *d*
bits, while reducing the worst case number of bits read to O(log
*d*), and keeping the number of bits written to a constant.
Finally, we improve our algorithm to read on average no more than
O(log^{(2c)} *d*) bits, while writing at most
2*c*+1 bits, for any non-negative integer *c*.