P49 - 格雷码

2026-09-07 00:00    #Haskell   #99题   #逻辑  

P49 - 格雷码

Gray codes

官方模块：Problems.P49　核心函数：gray

← P48 n 元布尔函数真值表 | P50 霍夫曼编码 →

题目描述

生成 n 位格雷码序列。格雷码的特点：相邻两个码字只有一位不同。

函数签名

1gray :: Int -> [String]

返回 [String]，其中每个字符串是一个格雷码（如 "001"）。

实现

方法一：递归镜像构造

1gray :: Int -> [String]
2gray 0 = [""]
3gray n
4  | n < 0     = []
5  | otherwise = map ('0' :) smaller ++ map ('1' :) (reverse smaller)
6  where smaller = gray (n - 1)

已知 n−1n-1 位序列 g，给每项加前缀 0，再给 g 的逆序加前缀 1。相邻项仅在首位不同或在原序列的镜像连接处不同。

方法二：二进制转格雷码

 1import Data.Bits ((.&.), shiftR, xor)
 2
 3gray :: Int -> [String]
 4gray 0 = [""]
 5gray n
 6  | n < 0     = []
 7  | otherwise = map (toGray n) [0..2^n - 1]
 8  where
 9    toGray :: Int -> Int -> String
10    toGray n i = pad n (binary (i `xor` (i `shiftR` 1)))
11    pad :: Int -> String -> String
12    pad n s = replicate (n - length s) '0' ++ s
13    binary :: Int -> String
14    binary 0 = "0"
15    binary 1 = "1"
16    binary i = binary (i `shiftR` 1) ++ (if i .&. 1 == 1 then "1" else "0")

利用公式 g=i⊕(i≫1)g = i \oplus (i \gg 1) 将整数 i 转为格雷码。先生成所有整数，再逐个转换。

方法三：迭代构造（不递归）

1gray :: Int -> [String]
2gray n
3  | n < 0     = []
4  | otherwise = go n [""]
5  where
6    go 0 result = result
7    go k result = go (k - 1) (map ('0' :) result ++ map ('1' :) (reverse result))

和方法一本质相同，但用迭代而非递归控制生成过程。

方法对比

方法特点
递归镜像经典定义，推荐
二进制转换公式利用位运算，适合硬编码
迭代构造避免递归，过程控制

测试

1>>> gray 2
2["00","01","11","10"]
3>>> length (gray 4)
416
5>>> gray 1
6["0","1"]

参考