This is the topic of my Thesis for my Master of Computer Science degree, where I looked at efficient algorithms to generate Gray codes and quasi-Gray codes. I looked at measuring efficiency in terms of the worst-case number of bits read and written to generate each string in the code, the average number of bits read, and the space efficiency, or the ratio of the number of bit strings generated to the dimension of the code.
Consider a sequence of bit strings of length d, such that 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. We examine the problem of efficiently generating such 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. Previous work on quasi-Gray codes has required at least one extra bit for the algorithms, such that at most 1/2 of the possible bit strings are generated, while our results do not require any extra bits. We show that when an algorithm is allowed to read all d bits in the worst case, it is possible to generate all 2d bit strings of a quasi-Gray code efficiently. When a smaller worst-case bound is required, we generate a factor of 1-O(d-t), for any constant t > 0, of the possible bit strings.
My full thesis can be read here.
I gave a presentation on this topic for the Carleton Algorithms Seminar series on March 17, 2010. My notes used for the talk can be viewed here.
An extended abstract paper version of my thesis will be appearing at the SWAT 2010 (12th Scandinavian Symposium and Workshops on Algorithm Theory) conference.