格雷码
格雷码（Gray code）是一个二进制数系，其中两个相邻数的二进制位只有一位不同。一个例子，\(3\) 位二进制数的格雷码序列为
\[
000,001,011,010,110,111,101,100
\]
注意序列的下标我们以 \(0\) 为起点，也就是说 \(G(0)=000,G(4)=110\)。
两种构造方法¶
手动构造¶
\(k\) 位的格雷码可以通过以下方法构造。我们从全 \(0\) 格雷码开始，按照下面策略：
- 翻转最低位得到下一个格雷码，（例如 \(000\to 001\)）；
- 把最右边的 \(1\) 的左边的位翻转得到下一个格雷码，（例如 \(001\to 011\)）；
交替按照上述策略生成 \(2^{k-1}\) 次，可得到 \(k\) 位的格雷码序列。
代码实现¶
vector<int> grayCode(int n) {
vector<int> data = {0};
int x = 0;
int N = pow(2, n) - 1;
for (int i = 0; i < N; i++) {
if ((i & 1) == 0) {
x = (x ^ 1);
} else {
int k = 0;
while (!(x & (1 << k))) k++;
x = x ^ (1 << (k+1));
}
data.push_back(x);
}
return data;
}
镜像构造¶
\(k\) 位的格雷码可以从 \(k-1\) 位的格雷码以上下镜射后加上新位的方式快速得到，如下图：
\[
\begin{matrix}
k=1\\
0\\ 1\\\\\\\\\\\\\\
\end{matrix}
\to \begin{matrix}\\
\color{Red}0\\\color{Red}1\\\color{Yellow}1\\\color{Yellow}0\\\\\\\\\\
\end{matrix}
\to \begin{matrix}
k=2\\
{\color{Red}0}0\\{\color{Red}0}1\\{\color{Yellow}1}1\\{\color{Yellow}1}0\\\\\\\\\\
\end{matrix}
\to \begin{matrix}\\
\color{Red}00\\\color{Red}01\\\color{Red}11\\\color{Red}10\\\color{Yellow}10\\\color{Yellow}11\\\color{Yellow}01\\\color{Yellow}00
\end{matrix}
\to \begin{matrix}
k=3\\
{\color{Red}0}00\\{\color{Red}0}01\\{\color{Red}0}11\\{\color{Red}0}10\\{\color{Yellow}1}10\\{\color{Yellow}1}11\\{\color{Yellow}1}01\\{\color{Yellow}1}00
\end{matrix}
\]
假定 \(k\) 位格雷码序列长度为 \(n\)，我们将这 \(k\) 位的格雷序列进行翻转，并追加到原有序列的尾部，得到长度为 \(2*n\) 的序列，此时新序列的前后两部分均为合法的格雷码。
考虑如何进行解决衔接点的合法性：我们可以对于序列的后半（翻转而来）的部分中的每个数进行「尾部」追加 \(1\) 的操作，确保链接点的两个数只有有一位二进制位不同，同时并不影响前后两半部分的合法性。
而且由于后半部分本身是由前半部分翻转而来，序列中的第一个数和最后一个数原本为同一个值，经过追加 \(1\) 的操作之后，首尾两个数的二进制表示只有一位不同，整个序列的合法性得以保证。
代码实现¶
vector<int> grayCode(int n) {
vector<int> data = {0};
int k = 0;
while (k++ < n) {
int m = data.size();
int x = 1 << (k-1);
for (int i = m - 1; i >= 0; i--) {
data.push_back(data[i] + x);
}
}
return data;
}