Please refer to: http://en.wikipedia.org/wiki/Gray_code
The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one digit.
The reflected binary code was originally designed to prevent spurious output from electromechanical switches. Today, Gray codes are widely used to facilitate error correction in digital communications such as digital terrestrial television and some cable TV systems.
Example Gray Codes: 2-bit Gray code 00 01 11 10
3-bit Gray code 000 001 011 010 110 111 101 100
4-bit Gray code 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | def isOdd(integer):
#assert isinstance(integer, int)
return integer % 2 == 1
def isEven(integer):
#assert isinstance(integer, int)
return integer % 2 == 0
def _list_to_string(li):
return ''.join(map(str, li))
class GrayCode(object):
def __init__(self, nbits):
self._nbits = nbits
self._grayCode = []
self.__generate()
def __getitem__(self, i):
return self._grayCode[i]
def __str__(self):
return str(self._grayCode)
__repr__ = __str__
def __iter__(self):
return self._grayCode.__iter__()
def __generate(self):
li = [0 for i in xrange(self._nbits)]
self._grayCode.append(_list_to_string(li))
for term in xrange(2, (1<<self._nbits)+1):
if isOdd(term):
for i in xrange(-1,-(self._nbits),-1):
if li[i]==1:
li[i-1]=li[i-1]^1
break
if isEven(term):
li[-1]=li[-1]^1
self._grayCode.append(_list_to_string(li))
class GrayCodeIterator(object):
def __init__(self, nbits):
self._nbits = nbits
def __iter__(self):
li = [0 for i in xrange(self._nbits)]
yield _list_to_string(li)
for term in xrange(2, (1<<self._nbits)+1):
if isOdd(term):
for i in xrange(-1,-(self._nbits),-1):
if li[i]==1:
li[i-1]=li[i-1]^1
break
if isEven(term):
li[-1]=li[-1]^1
yield _list_to_string(li)
if __name__=='__main__':
d = 4
codes=GrayCode(d)
print '%d digits gray codes:' % d
print codes
print 'Using Iterator:'
#for c in GrayCode(20):
# print c
for c in GrayCodeIterator(20):
print c
|
In the implementation, GrayCode returns a list of gray codes given by the number of bits, and GrayCodeIterator returns an iterator, with much higher memory efficiency.
Cool deal, I made it into an online utility here so people can try it out.
I'm assuming you're using the ugly reduce hack because sum complained at you? The right way to do it is like so, where li is your list: s = ''.join(str(i) for i in li) Lines 21-22 can be replaced with '__repr__ = __str__' if you put it after the def __str__ block. I'm not sure why you don't just generate the list of strings instead of converting it every time, or why you don't use a generator expression instead of returning the iter() of a list from a list comprehension, or why you're doing the isinstance assertion in isEven and isOdd. You can also rename the 'next' method of GrayCodeIterator to __iter__ and remove the old __iter__.
Ack, figures that it came out wrong because I didn't preview it. I forgot I had to have two newlines before and after code samples.
Hi, Aaron Gallagher. Thank you for your excellent suggesions. I have made some modifications, and it should look much more elegant right now. :)