---

1238. 循环码排列

• 标签：位运算、数学、回溯
• 难度：中等

题目链接

• 1238. 循环码排列 - 力扣

题目大意

描述：给你两个整数 $n$ 和 $start$。你的任务是返回任意一个包含 $0, 1, 2, ..., 2^n - 1$ 的排列 $p$，并且满足：

• $p[0] = start$
• $p[i]$ 和 $p[i+1]$ 的二进制表示形式只有一位不同
• $p[0]$ 和 $p[2^n - 1]$ 的二进制表示形式也只有一位不同（即首尾也满足相邻条件，形成一个环）

要求：返回满足条件的排列。

说明：

• $1 \le n \le 16$。
• $0 \le start \lt 2^n$。

示例：

• 示例 1：

输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
     所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]

• 示例 2：

输入：n = 3, start = 2
输出：[2,6,7,5,4,0,1,3]
解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)

解题思路

思路 1：格雷码 + 序列旋转

1. 核心思想

题目要求的排列，其实就是**格雷码（Gray Code）**序列。格雷码是一种二进制编码方式，特点是：

• 相邻的两个编码之间只有一位不同（这叫「单步特性」）。
• 对于 $n$ 位二进制数，格雷码序列包含全部 $2^n$ 个编码。
• 首尾编码也只有一位不同（这叫「循环码特性」）。

可以这样形象地理解：想象一个 $n$ 维立方体的顶点，每个顶点用一个 $n$ 位二进制数标记。从一个顶点出发，沿着棱走到下一个顶点，每次只能改变一个坐标（即一位二进制数）。格雷码就是一条恰好经过所有顶点一次，最后回到起点的「哈密顿回路」。

格雷码有一个非常简单通用的生成公式：

$$g(i) = i \oplus (i \gg 1)$$

其中 $i$ 从 $0$ 到 $2^n - 1$，$\oplus$ 表示按位异或运算，$\gg$ 表示右移运算。这样生成的序列自然满足相邻只有一位不同的条件。

但题目要求序列以 $start$ 开头，而标准格雷码是以 $0$ 开头的。不过格雷码序列有一个重要性质：循环移位后仍然满足相邻只有一位不同的条件（因为序列本身是循环的）。所以我们只需要在标准格雷码中找到 $start$，然后把序列「旋转」一下，让 $start$ 成为第一个元素即可。

2. 具体步骤

第 1 步：生成标准格雷码序列

遍历 $i$ 从 $0$ 到 $2^n - 1$，使用公式 $g(i) = i \oplus (i \gg 1)$ 生成每个格雷码，存入数组 $gray$。

第 2 步：找到 $start$ 的位置

在 $gray$ 中查找 $start$ 的下标 $idx$。

第 3 步：旋转序列

将以 $start$ 开头的序列构造出来：

$$result = gray[idx:] + gray[:idx]$$

即将原序列从 $idx$ 处「切断」，后半部分接上前半部分。

结合示例 1 走一遍：

$n = 2, start = 3$

生成标准格雷码：

• $i = 0$：$0 \oplus (0 >> 1) = 0 \oplus 0 = 0$
• $i = 1$：$1 \oplus (1 >> 1) = 1 \oplus 0 = 1$
• $i = 2$：$2 \oplus (2 >> 1) = 10_2 \oplus 01_2 = 11_2 = 3$
• $i = 3$：$3 \oplus (3 >> 1) = 11_2 \oplus 01_2 = 10_2 = 2$

标准格雷码序列：$[0, 1, 3, 2]$

找到 $start=3$ 的位置 $idx=2$。

旋转：$[3, 2] + [0, 1] = [3, 2, 0, 1]$

检查相邻元素二进制：（$11 \to 10$，$10 \to 00$，$00 \to 01$，$01 \to 11$），每对都只有一位不同，满足要求。

思路 1：代码

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        # 第 1 步：生成标准格雷码序列
        gray = []
        for i in range(1 << n):
            gray.append(i ^ (i >> 1))

        # 第 2 步：找到 start 的位置
        idx = gray.index(start)

        # 第 3 步：旋转序列，让 start 成为第一个元素
        return gray[idx:] + gray[:idx]

思路 1：复杂度分析

• 时间复杂度：$O(2^n)$，其中 $n$ 是位数。需要生成长度为 $2^n$ 的格雷码序列（$O(2^n)$），并在序列中查找 $start$ 的位置（最坏情况下也是 $O(2^n)$）。
• 空间复杂度：$O(2^n)$，需要存储完整的格雷码序列才能进行旋转操作。由于 $n \le 16$，$2^n \le 65536$，在合理范围内。