1
$\begingroup$

I want to iterate through the numbers $0,1,2,\dots,n-1$ in some order, where each number in the sequence differs by only one bit from the previous bit. I'm going to be using each number as an index into a matrix, and each index must be in the range $0..n-1$.

Gray codes look useful. The problem is that standard grey codes only work when $n$ is a power of two. Or, if we use a $k$-bit gray code (where $k = \lceil \lg n \rceil$), then some of the numbers in the gray code sequence will be larger than $n-1$, which will cause a segmentation fault when I try to access that index in the matrix.

So is there something like a gray code that works when $n$ is not a power of two? In other words, is there a way to construct a permutation of $0,1,\dots,n-1$ so that each number is at a Hamming distance of one from the previous number in the sequence?

$\endgroup$
2
$\begingroup$

Yes, such a Gray code sequence can be constructed for all $n$, even when $n$ is not a power of two. I'll describe how, below.

I will say that $a_0,\dots,a_{n-1}$ is a Gray code sequence for $0,1,\dots,n-1$ if each $a_i$ is in the range $0..n-1$, and if each $a_i$ differs from $a_{i-1}$ in a single bit position. Note that this generalizes the usual notion of a Gray code, to the situation where the numbers are not a power of two.

Let $n = 2^t + u$, where $u \le 2^t$. We'll use two steps:

  • First, recursively construct a Gray code sequence for the numbers $0..u-1$. Suppose the sequence is $x_0,x_1,\dots,x_{u-1}$. This means that each $x_i$ is in the range $0 \le x_i \le u-1$ (for each $i=0,1,\dots,u-1$), and each $x_i$ differs from $x_{i-1}$ in a single bit position (for $i=1,2,\dots,u-1$). This in turn gives us a Gray code sequence for the numbers $2^t,2^t+1,2^t+2,\dots,2^t+u-1$ by just adding $2^t$ to each element in the sequence: specifically, $2^t+x_0,2^t+x_1,\dots,2^t+x_{u-1}$.

  • Second, construct a Gray code sequence for the numbers $0..2^t-1$ that starts at the number $x_{u-1}$. A cool fact about the standard Gray code construction (for a power of two) is that it is cyclic, i.e., you can start anywhere and get to all the numbers, from that starting point. Let $y_0,y_1,\dots,y_{2^t-1}$ be this sequence. As mentioned, we have $y_0 = x_{u-1}$.

Now if we just concatenate these two sequences, we get an ordering of $0..n-1$ where each number in the sequence differs from its previous number by a single bit. In particular, the full sequence is

$$2^t+x_0,2^t+x_1,\dots,2^t+x_{u-1},y_0,y_1,\dots,y_{2^t-1},$$

with the $x$'s and $y$'s defined as above. This gives a simple and easy to implement construction for what you want.


Caution: Iterating through elements of the matrix in Gray code order will trash your cache. Caches are optimized for sequential access. You're doing random access (jumping around in the address space), so the caches will be useless and every memory access will be a miss in the cache. As a result, performance might suffer. Beware.

$\endgroup$
  • $\begingroup$ if $n=7$ then $t=2$ and $u=3$ so $n=4+3$. According to your answer then the sequence member $2^t+x_{u-1}$ has value $4+x_{2} = 4+3=7$ which is larger than n-1. So do I miss something? $\endgroup$ – Curious_Dim Apr 21 '17 at 19:50
  • $\begingroup$ @Curious_Dim, You went wrong in the first step. I don't know where $x_2=3$ came from, but that'll certainly never be true if you follow my construction. The first step is to construct a Gray code sequence $x_0,x_1,x_2$ for the numbers $0,1,2$. What sequence did you have in mind? Certainly no such sequence can have $x_2=3$, as every number in the sequence $x_0,x_1,x_2$ must be either 0, 1, or 2. For instance, one valid choice is $x_0=1$, $x_1=0$, $x_2=2$. That gives us a Gray code sequence for $4,5,6$, namely, $4+1,4+0,4+2$, i.e., $5,4,6$. That's the 1st step. Then you do the 2nd step. $\endgroup$ – D.W. Apr 21 '17 at 19:54
  • $\begingroup$ The gray code of 2 isn't 3? The sequence I have in mind is 0,1,3. To construct the gray code I use the rule gray_code(n)=n xor n/2 $\endgroup$ – Curious_Dim Apr 21 '17 at 20:06
  • $\begingroup$ @Curious_Dim, see 2nd paragraph of edited answer. There may be multiple different Gray code sequences, all valid; talking about "the Gray code" doesn't make sense. I recognize that there is a standard construction of a Gray code, but there are also other ways to do that meet all the requirements. At least, that's the terminology I use in my answer. Try re-reading it, with that in mind, and maybe it'll all make sense.... $\endgroup$ – D.W. Apr 21 '17 at 20:10
  • $\begingroup$ Choosing a permutation of the sequence{0..u-1} as a Gray code sequence $x_{0},x_{1},x_{2}$ for the first step, doesn't reduces to the original problem again? $\endgroup$ – Curious_Dim Apr 21 '17 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.