technical riddles
The question really asks if there is if the integers 0 .. 2^n 1 can be ordered in some way so that two consecutive integers differ in their binary representation by 1 bit.
A sequence with this property is called Gray code. Let's call Gn such a sequence of 2^n elements. It's clear that G1 = 0 1. Now if we know Gn1 we can easily find Gn by appending a 0 to every element in Gn1 and concatenating this sequence to the one we obtain by appending a 1 to every element in Gn1 and reversing this sequence.
A nice way of computing the kth term of Gn without computing the whole sequence is k ^ (k >> 1). You can find more about this here: http://www.library.cornell.edu/nr/bookcpdf/c202.pdf
Negruseri Cosmin
Monday, November 8, 2004
Recent Topics
Fog Creek Home
