如何生成相邻仅一位变化的n元二进制值全组合序列

嘿，你要找的这种序列其实就是经典的格雷码（Gray Code）！它的核心特性就是相邻两个组合之间恰好只有一个二进制位不同，完美匹配你的需求。

核心思路：格雷码的生成规则 #

格雷码的生成有几种常见方法，不管是针对2元还是扩展到n元都适用：

1. 递归法（直观易懂）

格雷码的递归逻辑非常清晰：

• 基础情况：1元二进制的格雷码是 [(1), (0)]（或者反过来，顺序不影响核心特性）
• 生成n元格雷码时：
  • 先得到n-1元的格雷码序列；
  • 给n-1元的每个组合前面添加1，作为新序列的前半部分；
  • 把n-1元的格雷码反转，给每个组合前面添加0，作为新序列的后半部分；
  • 拼接前半和后半，就是n元的格雷码序列。

举个2元的例子：

1. 1元格雷码：[(1), (0)]
2. 前半部分加1：[(1,1), (1,0)]
3. 反转1元格雷码得到[(0), (1)]，加0后得到[(0,0), (0,1)]
4. 拼接结果：[(1,1), (1,0), (0,0), (0,1)]

当然，格雷码的起始点和顺序可以灵活调整——比如你给出的示例[(1,0),(1,1),(0,1),(0,0)]，其实就是把上面的结果做了反转+移位，完全符合要求。

2. 公式法（高效简洁）

对于每个十进制数i（从0到2^n -1），对应的n位格雷码可以通过位运算直接计算：格雷码值 = i ^ (i >> 1)（^是异或运算，>>是右移一位）。之后把这个值转换成n位的二进制元组即可。

比如2元的情况，i从0到3：

• i=0 → 0 ^ 0 = 0 → 二进制00 → 元组(0,0)
• i=1 → 1 ^ 0 = 1 → 二进制01 → 元组(0,1)
• i=2 → 2 ^ 1 = 3 → 二进制11 → 元组(1,1)
• i=3 → 3 ^ 1 = 2 → 二进制10 → 元组(1,0)

最终序列：[(0,0), (0,1), (1,1), (1,0)]，相邻元组都只有一位差异。

代码实现（Python） #

这里给一个通用的n元格雷码生成函数，用公式法实现，高效且容易理解：

def generate_gray_code(n):
    gray_sequence = []
    # 遍历所有2^n个可能的十进制数
    for i in range(2 ** n):
        # 计算对应的格雷码十进制值
        gray_value = i ^ (i >> 1)
        # 转换为n位二进制字符串，高位在前，不足补0
        binary_str = bin(gray_value)[2:].zfill(n)
        # 转成元组加入序列
        gray_sequence.append(tuple(int(bit) for bit in binary_str))
    return gray_sequence

# 测试2元的情况
print(generate_gray_code(2))
# 输出：[(0, 0), (0, 1), (1, 1), (1, 0)]

# 如果想要你给出的示例序列，只需要反转结果即可
print(generate_gray_code(2)[::-1])
# 输出：[(1, 0), (1, 1), (0, 1), (0, 0)]

小提示 #

格雷码的序列并不是唯一的——只要满足相邻组合仅一位差异，任何合法的排列都可以。比如你可以选择不同的起始点，或者调整位的顺序（比如把元组的低位放在前面），核心逻辑不变。

内容的提问来源于stack exchange，提问作者Ark