Tuesday, November 25, 2008

99 problems - python - 49

Gray codes.

An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules. For example,

n = 1: C(1) = ['0','1'].
n = 2: C(2) = ['00','01','11','10'].
n = 3: C(3) = ['000','001','011','010',´110´,´111´,´101´,´100´].

Find out the construction rules and write a predicate with the following specification:

def gray(n):
if n == 0:
yield ""
else:
base = list(gray_code(n-1))

for code in base:
yield "0"+code

for code in reversed(base):
yield "1"+code

No comments: