Lesson 4

Interestingly, to obtain the Gray code, we need to slightly modify our recursive algorithm for generating binary words.

def gray_code(n):
    if n == 1:
        return ['0', '1']

    c = gray_code(n - 1)
    return ['0' + s for s in c] + ['1' + s for s in reversed(c)]

print(*gray_code(3))

0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

It is easy to see that the resulting order satisfies the stated properties. We will prove by induction that in the obtained order, any two adjacent strings, as well as the first and last strings, differ in exactly one position. The base case \(n=1\) is obvious. Let \(a,\dotsc,z\) be an order on strings of length \(n-1\). Then the order on strings of length \(n\) looks like: \[0a, \dotsc, 0z, 1z, \dotsc, 1a \ .\] In the sequences \(0a, \dotsc, 0z\) and \(1z, \dotsc, 1a\), everything is fine by assumption. There are two “junctions”: \((0z,1z)\) and \((1a,0a)\). They are also fine. In other words, we first recursively traverse all sequences starting with zero, then move to the layer of sequences starting with one, and traverse them (also recursively) in reverse order, after which we return. This is shown in the diagrams below.

• \(n=2\)

  



• \(n=3\)

  



• \(n=4\)