Is the following Greedy algorithm to generate Gray Codes always correct? I recently solved the basic problem of generating a n-bit Gray Code. The solution I used involved building larger-bit Gray Codes from smaller ones recursively (the solution I've seen on most websites).
However, I then had an idea for a Greedy Gray Code Algorithm: Start the Gray Code at 0 and at every step, find and change the single smallest bit such that we get a new, not-visited-before number. Keep on repeating this until we have exhausted all the 2^N possible numbers with N bits.
I was sure that this approach wouldn't work for some values of N, but so far, it has worked for all N from 1 to 30. This was quite surprising for me, especially as I haven't seen this Greedy approach mentioned anywhere as a solution to the Gray Code Problem.
So, my question is, does this Greedy algorithm for generating N-bit Gray Codes always work? Is there a proof of its correctness? Otherwise, what value of N causes this algorithm to not be able to generate a correct Gray Code?
Your construction results in the standard binary-reflected Gray code, a recursive construction of which is described on Wikipedia, for example. We can also describe it in a different way: to generate the $m$'th codeword from the $(m-1)$'th, flip the least significant 1 bit of $m$. For example, when $n=3$, we have:
$$
\begin{array}{c|c}
000 &amp; 000 \\
00\textbf{1} &amp; 00\textbf{1} \\
0\textbf{1}1 &amp; 0\textbf{1}0 \\
01\textbf{0} &amp; 01\textbf{1} \\
\textbf{1}10 &amp; \textbf{1}00 \\
11\textbf{1} &amp; 10\textbf{1} \\
1\textbf{0}1 &amp; 1\textbf{1}0 \\
10\textbf{0} &amp; 11\textbf{1}
\end{array}
$$