Gray Code
An n-bit Gray code is a sequence if 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(2) = ['000', '001', '011', '010', '110', '111', '101', '100'].
Find out the construction rules and write a predicate with the following specification:
%gray(N,C):- C is the N-Bit Gray code
Gray Code的规则是：
- N不为1时，先将
0拼接到gray(N-1)中的每一个元素，再把1拼接到gray(N-1)的反序列表中的每一个元素，最后拼接两个结果列表。 - N为1时，值为
['0', '1']
gray(N) = prepend('0', gray(N-1)) + prepend('1', reverse(gray(N-1)))
gray(1) = ['0', '1']
照例先写单元测试：
from python99.logic_codes.p304 import gray
def test_gray():
assert gray(1) == ['0','1']
assert gray(2) == ['00','01','11','10']
assert gray(3) == ['000','001','011','010','110','111','101','100']
assert gray(4)==['0000','0001','0011','0010','0110','0111','0101','0100','1100','1101','1111','1110','1010','1011','1001','1000']
Gray Code的规则是以递归方式定义的，使用递归算法实现是最直接有效的。代码实现：
def gray(n):
if n == 1:
return ['0', '1']
return ['0'+e for e in gray(n-1)] + ['1'+e for e in reversed(gray(n-1))]
- 当n为1时，返回
['0', '1']。 - 当n大于1时，先将
0拼接至gray(n-1)中的每一个元素。再把gray(n-1)反序，把1拼接至反序列表中的每一个元素。最后将两个结果列表拼接起来。