Gray code

Problem Setup

Let’s consider the following scenario:

In front of you are $n$ switches. Each switch can either be in the ON or OFF state, and they all start in the OFF position.

These switches are the key to a safe, which can only be unlocked when the switches are set in a specific combination.

However, you’ve forgotten the correct combination.

Your goal is to try different switch combinations to unlock the safe, but you want to find the most efficient way to do so.

The simplest solution is to perform a brute force search, testing all $2^n$ possible switch states.

For example, when $n=3$, you would test the following:

This method works, but the number of switch toggles required can be quite high.

For instance, transitioning from $0$ -> $1$ only requires toggling the rightmost switch, but transitioning from $1$ -> $2$ requires toggling both the middle and rightmost switches.

In total, the number of switch presses is 11.

Since that seems a bit tiring, we now ask, “Is there a way to reduce the number of toggle actions?”

Case for $n=2$

If we fix the first $0$, the remaining $2^n-1$ numbers can be arranged in $(2^n-1)!$ different ways.

While it’s difficult to check all possible sequences for minimizing the number of switch toggles, for $n=2$, there are only 6 possibilities, so we can check them all.

(1) 0,1,2,3

The total number of switch changes is 4.

(2) 0,1,3,2

The total number of switch changes is 3.

(3) 0,2,1,3

The total number of switch changes is 4.

(4) 0,2,3,1

The total number of switch changes is 3.

(5) 0,3,1,2

The total number of switch changes is 5.

(6) 0,3,2,1

The total number of switch changes is 5.

Conclusion

For $n=2$, the sequences $00,01,11,10$ or $00,10,11,01$ result in the minimum number of switch changes, which is 3.

Case for $n=3$

Next, let’s consider the case when $n=3$. This time, checking all possible sequences would involve $7!=5040$ possibilities, which is far too many to enumerate.

So, we aim from the start to minimize the number of switch changes to 7.

By considering each number from $0$ to $2^n-1$ as a vertex, and connecting vertices that differ by exactly one bit, we get a graph resembling a cube, as shown on the left in the figure below.

To find the optimal switch sequence, we need to trace a path through this graph that visits each vertex exactly once, which will give us the desired sequence.

Fundamentally distinct sequences of bit changes correspond to the three paths shown in the right-side figure.

In general, such paths are called Hamiltonian paths.

Taking into account symmetry, we find that even when restricted to paths starting at $000$, there are still $3\cdot 3\cdot 2=18$ distinct sequences (since there are 3 choices for the first step, 2 for the second).

General Case for $n$

Using the method described above for $n=3$, the problem can be interpreted as one of finding a Hamiltonian path for the $n$-dimensional hypercube graph.

For $n=2$, there were 2 possibilities, and for $n=3$, there are 18 distinct paths, so it’s likely that there are many such paths for larger $n$.

One possible approach to constructing such a sequence is to use the Hamiltonian path for the $(n-1)$-dimensional hypercube as a base.

After some thought, we can devise the following algorithm:

First, apply the known sequence to the lower $(n-1)$ bits while keeping the most significant bit at $0$.

Once we reach the end of the sequence, flip only the most significant bit to $1$.

Next, apply the reverse of the $(n-1)$-bit sequence to the lower bits.

For example, starting with the sequence for $n=1$ as $0,1$, we can extend this algorithm to construct sequences for $n=2$, $3$, and $4$ as follows:

For $n=2$: $00,01,11,10$ For $n=3$: $000,001,011,010,110,111,101,100$ For $n=4$: $0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1111,1110,1010,1011,1001,1000$

This algorithm allows us to generate an infinite sequence of numbers.

This sequence is commonly referred to as the Gray code.

The Number of Gray Codes

While “Gray code” often refers specifically to the sequence generated by the algorithm described above, the term can also refer more generally to any sequence in which adjacent terms differ by exactly one bit.

As we have seen, this is equivalent to finding a Hamiltonian path on the $n$-dimensional hypercube graph.

We’ve already determined that for $n=1$, there is 1 Gray code; for $n=2$, there are 2; and for $n=3$, there are 18. How does this number increase as $n$ grows?

• For $n=4$, there are 5,712 Gray codes.
• For $n=5$, there are 5,859,364,320.

The number grows rapidly.

This sequence is listed in OEIS A003043.