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 kth element of the binary reflected Gray sequence, irrespective of the bit length. The kth 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.
Programming Praxis 
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.
; Generate a list of binary lists representing a binary reflected gray code (define (binary-reflected-gray-code/binary-list bits) (cond [(zero? bits) '(())] [else (define rest (binary-reflected-gray-code/binary-list (- bits 1))) (append (map (curry cons 0) rest) (map (curry cons 1) (reverse rest)))])) ; Convert a list of binary digits to decimal (define (binary-list->decimal ls) (let loop ([ls ls] [acc 0]) (cond [(null? ls) acc] [else (loop (cdr ls) (+ (* 2 acc) (car ls)))]))) ; Generate a list of n-bit decimal numbers using a binary reflected gray code (define (binary-reflected-gray-code/decimal bits) (map binary-list->decimal (binary-reflected-gray-code/binary-list bits)))(pfft efficiency…)
In Haskell:
import Control.Monad import Data.Bits import Numeric import Text.Printf -- The n'th BRGC. From Warren's "Hacker's Delight", 2nd ed. gray :: Integer -> Integer gray n = (n `shiftR` 1) `xor` n nBitGrays n = [gray (i-1) | i <- [1..2^n]] printGrays n = mapM_ (printf "%0*s\n" n . base2) $ nBitGrays n :: IO () where base2 n = showIntAtBase 2 ("01" !!) n ""Running it in ghci:
(defn step [elems] (let [zero-prefixed (map #(str "0" %) elems) reversed (reverse elems) one-prefixed (map #(str "1" %) reversed)] (concat zero-prefixed one-prefixed))) (defn get-BRGC [n] (loop [i 1 elems ["0" "1"]] (if (= i n) elems (recur (inc i) (step elems)))))(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:
(defn brgc [n] (loop [i 0 xs [0] P 1] (if (= i n) xs (recur (inc i) (concat xs (map #(+ P %) (reverse xs))) (+ P P)))))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:
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)]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 gcHere’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:
#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int n = 1 << atoi(argv[1]); int k = 0; for (int i = 0; i<n; i++) { printf("%d\n", k); int r = (i+1)&~i; k ^= r; } }