## Binary Reflected Gray Code

### May 2, 2014

This is a simple recursion on sequences represented as lists, with the sequence (0) as the recursive base:

(define (gray n) (define (add x) (lambda (y) (+ x y))) (let loop ((n n) (g 1) (gs (list 0))) (if (zero? n) gs (loop (- n 1) (+ g g) (append gs (map (add g) (reverse gs)))))))

The magic is in the last line. The next-smaller sequence is in variable *gs*, which is reversed, then the next-larger power-of-two, which is accumulated in variable *g*, is added to each item of the reversed sequence, and finally the two lists are appended. The `add`

function is a curried form of addition. Here are the first several Gray sequences:

> (gray 0) (0) > (gray 1) (0 1) > (gray 2) (0 1 3 2) > (gray 3) (0 1 3 2 6 7 5 4) > (gray 4) (0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8) > (gray 5) (0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16) > (gray 6) (0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32) > (gray 7) (0 1 3 2 6 7 5 4 12 13 15 14 10 11 9 8 24 25 27 26 30 31 29 28 20 21 23 22 18 19 17 16 48 49 51 50 54 55 53 52 60 61 63 62 58 59 57 56 40 41 43 42 46 47 45 44 36 37 39 38 34 35 33 32 96 97 99 98 102 103 101 100 108 109 111 110 106 107 105 104 120 121 123 122 126 127 125 124 116 117 119 118 114 115 113 112 80 81 83 82 86 87 85 84 92 93 95 94 90 91 89 88 72 73 75 74 78 79 77 76 68 69 71 70 66 67 65 64)

Since the *n*-bit Gray sequence is embedded in the first half of the *n*+1-bit Gray sequence, it makes sense to talk about the *k*th element of the binary reflected Gray sequence, irrespective of the bit length. The *k*th element of the Gray sequence is *k* ⊕ ⌊*k* / 2⌋,where ⊕ is the logical `xor`

operator, which can be expressed simply in C as `(k >> 1) ^ k`

. Thus, here is another way to write the *n*-bit gray sequence:

(define (nth-gray n) (bitwise-xor n (ash n -1))) (define (gray n) (do ((k 0 (+ k 1)) (gs (list) (cons (nth-gray k) gs))) ((= k (expt 2 n)) (reverse gs)))) > (nth-gray 0) 0 > (nth-gray 1) 1 > (nth-gray 2) 3 > (nth-gray 3) 2 > (nth-gray 4) 6 > (nth-gray 5) 7 > (nth-gray 6) 5 > (nth-gray 7) 4

You can run the program at http://programmingpraxis.codepad.org/ndutMKZE.

Function “gray2” in:

http://matthewarcus.wordpress.com/2014/04/07/ringing-the-changes/

(with m[i] = 2 for each i).

Misread at first, so I did it in binary lists rather than decimal, but it’s straight forward enough to convert.

(pfft efficiency…)

In Haskell:

Running it in ghci:

(no handling for 0-bit sequence!)

After looking into your code, I realized that I misunderstood the exercise as well: numbers ant not bit strings are required. After re-thinking my solution I boiled down all string manipulations to algebraic operations and got pretty much your solution:

A recursive version:

[sourcecodelang=”python”]

def brgc(n):

if n == 1:

return [0, 1]

else:

val = brgc(n-1)

bit = 1 << (n-1)

return val + [bit+v for v in reversed(val)]

[/sourcecode]

And an iterative version:

def brgc(n):

gc = [0]

for b in (1<<i for i in range(n)):

gc.extend(c+b for c in reversed(gc))

return gc

With proper formatting this time.

A recursive version:

And an iterative version:

Here’s another nice bit-twiddling solution – the ruler function (number of trailing 0s) for i+1 tells us which bit to flip to get the i+1th gray code: