//
Uncategorized

Generating Gray Codes and deBruijn Sequences

Gray Codes

Gray codes are min-change sequences of bit-strings where each successive string is obtained by making a single bit change. The Binary Reflected Gray Code is obtained by changing bits according to the same sequence as the solution to the Towers of Hanoi. BRGC can also be obtained recursively by reversing the code generated in each successive sequence while adding or prepending 0 to first half and prepending 1 on second half.

http://pastebin.com/Mg1uPpgm

(defn towers [n]
(cond
(= n 1 ) (list  1)
:else
(concat (towers (dec n)) (list n) (towers (dec n)))))

(defn gray [n]
(cond
(= n 1) '((0) (1))
:else   (let [first  (map (fn[s] (cons 0 s)) (gray (dec n)))
second (map (fn[s] (cons 1 s)) (reverse (gray (dec n))))]
(concat first second))))
(gray 3)

(defn rank
(cond
(empty? code) 0
:else  (cond  (= 0 (first code ))   (rank (rest code))
:else  (dec  (-  (Math/pow 2 (count code))  (rank

(rank '( 1 1 0))
#=&gt; 4


DeBruin Sequences of order-n is string of 2^n-bits so that every n-bit string can be located as a substring (allowing wrap around). There are 2^(2^(n-1)-n) different sequences with this property.

More generally, a k-ary De Bruijn sequence B(kn) of order n, is a cyclic sequence of a given alphabet A with size k for which every possible subsequence of length n in appears as a sequence of consecutive characters exactly once.

Each B(kn) has length kn.

There are $\dfrac{\left(k!\right)^{k^{n-1}}}{k^n}$ distinct De Bruijn sequences B(kn).

The De Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional De Bruijn graph over k symbols (or equivalently, a Eulerian cycle of a (n − 1)-dimensional De Bruijn graph).

Code for Generating Debruijn Sequences

def comp(a):
return str(1-int(a))

from operator import xor

def xor_reduce(x):
#in string --&gt; out bool
return reduce(xor, map(int, x))

def xor_iscan(x):
return ''.join(str(xor_reduce(x[:i]))
for i in range(1, len(x)+1))

def nextDeB(w, i, k):
C = xor_iscan(w);
Cbar =&quot;&quot;.join(comp(a) for a in  C)
part1 = C[: i - k]
part2 = Cbar[i - 1 + k:]
part3 = Cbar[: i - 1 + k]
part4 = C[i - k:]
return part1 + part2 + part3 + part4

def GenDeB (x):
if len(x) == 0:
return &quot;1100&quot;
elif len(x) == 1:
if x[0] == '0':
return &quot;10111000&quot;
else:
return &quot;11101000&quot;
else:
return nextDeB(GenDeB(x[:-1]), 2**len(x)+(-1)**int(x[-2]), int(x[-1]))

print GenDeB('10001010011')



The call GenDeB('10001010011') produces a string (image at the top) of an order-13 debruijn sequence of length 8192 = 2^13. The function GenDeB will produce 2^11 such sequences one for each 11-bit string used as argument.

Another method to generate deBruijn Sequences
A simple method to remember is called "prefer 1s". The idea is that you start with all 0s then always prefer to append 1, but if it leads to a redundancy in the sequence you opt instead for a 0. Hence, consider the following prefer 1 sequence 00011101 - this is a deBruin sequence.

def prefer1(n):
myd=set()
state=0
while True:
trans= (2*state +1) % (1&lt;&lt;n)
if trans not in myd:
yield '1'
else:
trans-=1
yield '0'
state= trans
if state==0:
break

for i in prefer1(4):
print i,
#=&gt;1 1 1 1 0 1 1 0 0 1 0 1 0 0 0 0

# to eliminate spaces we have the following
import sys
for i in prefer1(6):
sys.stdout.write(i)
#=&gt;1111110111100111010111000110110100110010110000101010001001000000