On 5/29/14, Warren D Smith <warren.wds@gmail.com> wrote:
The "Gray code" is a fast way to produce the integers 0,1,2,..2^p-1 in an order such that each differs from predecessor in exactly 1 bit.
Q1 (easy). Find an anti-Gray code where each differs from predecessor in exactly p-1 bits.
Q2 (not so easy). Find a "mid-gray" code where each differs from predecessor in exactly p/2 bits (p>1 even). Note this is impossible if p is a multiple of 4.
--actually, here is a solution. Maybe not a very nice solution, but it seems to work. A1. Just use gray code except bitwise-complement every other number. A2(i). If p is multiple of 4, then each word differs from previous in an even number of positions, causing parity to be preserved, meaning you lose because one parity is never accessed. A2(ii). Let p=2*q with q odd. Use A1 with a circular (Hamiltonian tour) Gray code to fidoodle the least-significant q+1 bits. When you get done [2^(q+1) steps], then do a single gray code step on the remaining (i.e. upper) q-1 bits while at the same time altering the lower q+1 bits in q-1 places (it does not matter what alteration). Then do it again. Keeping going in this way, we ultimately generate every p-bit word exactly once, with successors differing in exactly p/2 positions. Note also this answer is readily generalizable to allow generating all p-bit words in a manner such that each differs from preceding in exactly k bits. Works for any p>k>0 with k odd you want. And it is same algorithmic efficiency as the Gray code is, up to constant additive and multiplicative factors.