位运算题目：循环码排列

题目

标题和出处

标题：循环码排列

出处：1238. 循环码排列

难度

5 级

题目描述

要求

给定两个整数 $\text{n}$ 和 $\text{start}$，返回 $\text{(0,1,2,}\dots {\text{,2}}^{\text{n}}-\text{1)}$ 的任意排列 $\text{p}$，满足以下条件：

• $\text{p[0]}=\text{start}$
• $\text{p[i]}$ 和 $\text{p[i}+\text{1]}$ 的二进制表示形式只有一位不同。
• $\text{p[0]}$ 和 ${\text{p[2}}^{\text{n}}-\text{1]}$ 的二进制表示形式也只有一位不同。

示例

示例 1：

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

示例 2：

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

数据范围

• $\text{1}\le \text{n}\le \text{16}$
• $\text{0}\le \text{start}<{\text{2}}^{\text{n}}$

前言

这道题要求对于给定的整数 $n$ 生成包含 $0$ 到 $2^n-1$ 的排列，要求排列中的任意两个相邻元素之间以及首个整数和最后一个整数之间都满足二进制表示只有一位不同，该性质与格雷码序列的性质相同。因此，这道题的本质是计算 $n$ 位格雷码序列。

由于这道题还指定了排列的首个整数 $\text{start}$，因此需要从 $\text{start}$ 开始按格雷码序列的顺序遍历每个整数，得到有效的排列。

可以使用「格雷编码」的做法得到 $n$ 位格雷码序列，然后根据排列的首个整数 $\text{start}$ 得到有效的排列。也可以利用格雷码序列的性质，一步生成有效的排列。

解法一

思路和算法

用 $G_n$ 表示 $n$ 位格雷码序列，其中 $n\ge 0$，$G_n$ 由 $2^n$ 个数组成，规定 $G_0=[0]$。为了使格雷码序列的结果唯一，当 $n>0$ 时规定 $G_n[1]=1$。

对于 $k\ge 0$，假设 $k$ 位格雷码序列 $G_k$ 已知，其长度是 $2^k$。根据 $G_k$ 可以生成 $k+1$ 位格雷码序列 $G_{k+1}$，做法如下。

• 对于 $0\le i<2^k$，$G_{k+1}[i]=G_k[i]$。

• 对于 $2^k\le i<2^{k+1}$，$G_{k+1}[i]=G_k[2^{k+1}-1-i]+2^k=G_{k+1}[2^{k+1}-1-i]+2^k$。

根据上述做法，从 $G_0$ 开始按照位数递增的顺序依次生成格雷码序列，直到得到 $n$ 位格雷码序列 $G_n$。

由于排列的首个整数 $\text{start}$ 满足 $0\le \text{start}<2^n$，因此在 $G_n$ 中一定包含 $\text{start}$。在生成 $G_n$ 的过程中得到 $\text{start}$ 的下标 $\text{startIndex}$，当得到完整的 $G_n$ 之后，从下标 $\text{startIndex}$ 开始遍历每个整数，当遍历 $2^n$ 个整数之后即可得到有效的排列。

代码

class Solution {public List<Integer> circularPermutation(int n, int start) {List<Integer> gray = new ArrayList<Integer>();gray.add(0);int startIndex = 0;int index = 1;int count = 1;for (int i = 1; i <= n; i++, count *= 2) {for (int j = count - 1; j >= 0; j--, index++) {int curr = gray.get(j) | count;gray.add(gray.get(j) | count);if (curr == start) {startIndex = index;}}}List<Integer> permutation = new ArrayList<Integer>();for (int i = 0, j = startIndex; i < count; i++, j = (j + 1) % count) {permutation.add(gray.get(j));}return permutation;}
}

复杂度分析

• 时间复杂度：$O(2^n)$，其中 $n$ 是给定的整数。当格雷码序列的位数是 $n$ 时共有 $2^n$ 个数，生成每个数的时间都是 $O(1)$，生成格雷码序列之后需要从 $\text{start}$ 开始遍历每个数得到排列，因此时间复杂度是 $O(2^n)$。

• 空间复杂度：$O(2^n)$，其中 $n$ 是给定的整数。格雷码序列需要 $O(2^n)$ 的空间。

解法二

思路和算法

解法一需要首先生成格雷码序列，然后遍历生成的格雷码序列得到有效的排列。有一种更快的做法，不需要首先生成格雷码序列，而是可以直接生成有效的排列。

对于给定的整数 $n$，当 $0\le i<2^n$ 时，$i$ 的格雷码是 $G_n[i]=(i>>1)\oplus i$，格雷码序列的首个整数是 $0$。为了得到首个整数是 $\text{start}$ 的排列，只要将格雷码序列中的每个整数与 $\text{start}$ 做按位异或运算即可，即 $p[i]=(i>>1)\oplus i\oplus \text{start}$。

使用该方法即可一步生成有效的排列。

证明

考虑 $n$ 位格雷码序列 $G_n$，满足 $G_n[0]$ 和 $G_n[2^n-1]$ 的二进制表示恰好有一位不同且对于任意 $0\le i<2^n-1$ 都有 $G_n[i]$ 和 $G_n[i+1]$ 的二进制表示恰好有一位不同。

考虑 $G_n$ 中的两个相邻整数或者首尾整数 $G_n[j]$ 和 $G_n[k]$，满足 $G_n[j]$ 和 $G_n[k]$ 的二进制表示恰好有一位不同。对于排列 $p$，有 $p[j]=G_n[j]\oplus \text{start}$ 和 $p[k]=G_n[k]\oplus \text{start}$。当 $0\le t<n$ 时，用 $b(t)$ 表示整数 $b$ 的二进制表示的从低到高的第 $t$ 位，则 $p[j](t)=G_n[j](t)\oplus \text{start}(t)$，$p[k](t)=G_n[k](t)\oplus \text{start}(t)$，因此 $G_n[j](t)=G_n[k](t)$ 等价于 $p[j](t)=p[k](t)$，$G_n[j](t)\ne G_n[k](t)$ 等价于 $p[j](t)\ne p[k](t)$。根据 $G_n[j]$ 和 $G_n[k]$ 的二进制表示恰好有一位不同可知，$p[j]$ 和 $p[k]$ 的二进制表示也恰好有一位不同。

因此，$p$ 是有效的排列。

代码

class Solution {public List<Integer> circularPermutation(int n, int start) {List<Integer> permutation = new ArrayList<Integer>();int total = 1 << n;for (int i = 0; i < total; i++) {permutation.add((i >> 1) ^ i ^ start);}return permutation;}
}

复杂度分析

• 时间复杂度：$O(2^n)$，其中 $n$ 是给定的整数。排列共有 $2^n$ 个数，生成每个数的时间都是 $O(1)$。

• 空间复杂度：$O(1)$。注意返回值不计入空间复杂度。