这神秘序列，为何每个数都和前一个差1，却无重复？
摘要：背景 昨日写题的时候，偶遇一道神奇的构造题，题目是这样的： 构造一个长度为(2^n)的序列(p_0,p_1,…,p_{2^n−1})，使得相邻两项异或值之和最小。 这道题很容易就可以看出，如果要构造一个使得相邻两项异或值之和最小的序
背景
昨日写题的时候，偶遇一道神奇的构造题，题目是这样的：
构造一个长度为\(2^n\)的序列\(p_0,p_1,…,p_{2^n−1}\)，使得相邻两项异或值之和最小。
这道题很容易就可以看出，如果要构造一个使得相邻两项异或值之和最小的序列，就要保证每个元素与相邻元素间在二进制下仅有一位的差距，而这样的序列显然会按照有效二进制位数升序排列，因此我很快就想到了这样一个贪心策略：首先将0放进排列尾部，然后每次从小到大尝试改变尾部的二进制位，如果得到的是新数就更新排列，这里的从小到大尝试改变尾部的二进制位指的是：当数已经存在于生成的答案序列中时，尝试改变更高一位的二进制位。举个例子：
0
0 1
(尝试改变0的倒数1位,得到1,成功)
0 1 3
(尝试改变1的倒数1位,得到0,但0在排列中,失败,尝试改变1的倒数第2位,得到3,成功)
0 1 3 2
(尝试改变3的倒数1位，得到2，成功)
0 1 3 2 6
(尝试改变2的倒数1位,得到3,失败,尝试改变2的倒数第2位,得到0,失败,尝试改变2的倒数第3位,得到6,成功)
0 1 3 2 6 7 5 4
这就是我所想到的贪心思路，它是正确的，代码如下：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int m = 1 << n;
vector<int> ans;
vector<bool> vis(m, false);
int cur = 0;
ans.push_back(cur);
vis[cur] = true;
while ((int)ans.size() < m) {
for (int i = 0; i < n; i++) {
int nxt = cur ^ (1 << i);
if (!vis[nxt]) {
cur = nxt;
ans.push_back(cur);
vis[cur] = true;
break;
}
}
}
for (int i = 0; i < m; i++) {
cout << ans[i] << " \n"[i == m - 1];
}
return 0;
}
转折
当我完成这道题后，还没来得及欣喜，就在看题解时发现了这道题原来另有说法，这道题目所要求构造的序列其实是一个非常经典的序列，该序列构造的规则是一个叫做格雷码的二进制数字系统，是由贝尔实验室的Frank Gray于20世纪40年代提出。它具有许多优点。
格雷码
基本定义
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）
性质
单位距离性
相邻格雷码之间的二进制仅有一位不同
循环性
任意连续\(2^k\)个格雷码其首尾仍符合单位距离性，即首位间二进制仅有一位不同
子立方体封闭性
在 n 维格雷码序列中，任意连续 \(2^k\) 项（从 \(2^k\) 的整数倍位置开始）恰好构成一个 k 维子立方体的格雷码。