Gray Codes

The binary interpretation of bits is only one possible ordering of the possible states in an n-bit register. A gray code is another interpretation where adjacent numbers vary in only one bit. wikipedia

The important idea is that we can assign meaning to bit patterns. See also Complement Representation

We can use the binary representation of numbers to compute a maximal sequence of bit patterns where only one bit changes between each element.

We begin with helper functions to print objects and compute single bit constants.

p = (val) -> console.log JSON.stringify val bit = (num) -> Math.pow 2, num

We'll set up our computation for a given number of bits. We'll keep lists of used and unused values.

bits = 6 used = [last = 0] unused = [1..(bit(bits)-1)]

Next will choose a number from unused and add it to used. We search unused choices for a possible choice made by flipping progressively larger bits.

next = -> for b in [0..bits-1] n = last ^ bit(b) i = unused.indexOf n if i>= 0 unused.splice i, 1 used.push last = n return true return false

We'll keep working until we can't continue.

'work' while next()

[ 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 ]

Pseudorandom sequences often go through most possible states of a counter. See Random Hello World.