Gray code in q

It is easy to construct binary n-bit Gray code in q using the recursive reflection-prefixing technique:

q)gc:{$[x;(0b,/:a),1b,/:reverse a:.z.s x-1;1#()]}
q)show gc 4
0000b 0001b 0011b 0010b 0110b 0111b 0101b 0100b
1100b 1101b 1111b 1110b 1010b 1011b 1001b 1000b

It is also possible to construct the above iteratively using the formula n \oplus \lfloor n/2 \rfloor:

q).q.xor:{not x=y}
q)gc_iter:{(0b vs x) xor (0b vs x div 2)}
q)show (-4#gc_iter@) each til 16
0000b 0001b 0011b 0010b 0110b 0111b 0101b 0100b
1100b 1101b 1111b 1110b 1010b 1011b 1001b 1000b

To check that indeed exactly one bit is flipped each time:

q)check:{x[0] (sum@xor)': 1_x}
q)check gc 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

To identify the position of the bit that was flipped:

q)pos:{raze x[0] (where@xor)': 1_x}
q)pos gc 5
4 3 4 2 4 3 4 1 4 3 4 2 4 3 4 0 4 3 4 2 4 3 4 1 4 3 4 2 4 3 4

If we think about it, there is no reason why we have to prefix. We could do suffix as well:

q)gc:{$[x;(a,\:0b),(reverse a:.z.s x-1),\:1b;1#()]}
q)show gc 4
0000b 1000b 1100b 0100b 0110b 1110b 1010b 0010b
0011b 1011b 1111b 0111b 0101b 1101b 1001b 0001b
q)check gc 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
q)pos gc 5
0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 4 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0

In fact, if we are only interested in the positions that need to be flipped, we can use this instead:

q)gcpos:{$[x;a,n,a:.z.s n:x-1;()]}
q)gcpos 5
0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 4 0 1 0 2 0 1 0 3 0 1 0 2 0 1 0

Such a sequence of positions is useful if we are using Gray code to efficiently enumerate the non-zero points spanned by a set of basis vectors:

q)basis:(1100000b;0111001b;0000011b)
q){x xor y} scan basis gcpos count basis
1100000b
1011001b
0111001b
0111010b
1011010b
1100011b
0000011b

Update (20090927): Once again, Attila has beaten me at q-golf :-) Here is his formulation:

gc:{x{(0b,/:x),1b,/:reverse x}/1#()}
Posted in k&q. Tags: , . Leave a Comment »