What is the Circular Permutation in Binary Representation problem?

This problem involves generating a permutation of numbers from 0 to 2^n - 1 where each adjacent pair of numbers differs by exactly one bit in their binary representation.

How do you approach solving the Circular Permutation in Binary Representation?

A backtracking approach with pruning works well, leveraging Gray code to generate the sequence. Bit manipulation helps efficiently transition between numbers with one-bit differences.

What is Gray code and how does it help in this problem?

Gray code is a binary numeral system where two consecutive numbers differ by exactly one bit. It helps generate the permutation efficiently while satisfying the problem's constraints.

What are common pitfalls in solving the Circular Permutation in Binary Representation?

Common pitfalls include not implementing pruning in backtracking, incorrectly transitioning between numbers, and failing to use Gray code for efficiency.

How does backtracking work in the Circular Permutation problem?

Backtracking explores all possible solutions while pruning invalid paths early. By ensuring that each transition between numbers differs by exactly one bit, it helps generate the correct permutation.

#1238

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

循环码排列

给你两个整数 n 和 start 。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p ，并且满足： p[0] = start p[i] 和 p[i+1] 的二进制表示形式只有一位不同 p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同示例 1：输入： n = 2…

数学回溯位运算

题目描述

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

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

示例 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 <= n <= 16
0 <= start < 2^n

lightbulb

解题思路

方法一：二进制码转格雷码

我们观察题目中的排列，可以发现，它的二进制表示中，任意两个（包括首尾）相邻的数只有一位二进制数不同。这种编码方式就是格雷码，它是我们在工程中会遇到的一种编码方式。

二进制码转换成二进制格雷码，其法则是保留二进制码的最高位作为格雷码的最高位，而次高位格雷码为二进制码的高位与次高位相异或，而格雷码其余各位与次高位的求法相类似。

假设某个二进制数表示为 $B_{n-1}B_{n-2}...B_2B_1B_0$ ，其格雷码表示为 $G_{n-1}G_{n-2}...G_2G_1G_0$ 。最高位保留，所以 $G_{n-1} = B_{n-1}$ ；而其它各位 $G_i = B_{i+1} \oplus B_{i}$ ，其中 $i=0,1,2..,n-2$ 。

因此，对于一个整数 $x$ ，我们可以用函数 $gray(x)$ 得到其格雷码：

int gray(x) {
    return x ^ (x >> 1);
}

我们可以直接将 $[0,..2^n - 1]$ 这些整数转换成对应的格雷码数组，然后找到 $start$ 在格雷码数组中的位置，将格雷码数组从该位置开始截取，再将截取的部分拼接到格雷码数组的前面，就得到了题目要求的排列。

时间复杂度 $O(2^n)$ ，空间复杂度 $O(2^n)$ 。其中 $n$ 为题目给定的整数。

1

2

3

4

5

6

class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        g = [i ^ (i >> 1) for i in range(1 << n)]
        j = g.index(start)
        return g[j:] + g[:j]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates an understanding of Gray code and its application in generating valid sequences.
question_mark
Candidate efficiently uses bit manipulation to minimize unnecessary computation.
question_mark
Candidate identifies and explains the pruning strategy used in backtracking for optimization.

warning

常见陷阱

外企场景

error
Failing to implement pruning in backtracking, leading to inefficient searches.
error
Incorrectly transitioning between numbers that don't differ by exactly one bit.
error
Not leveraging Gray code for an optimal solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Changing the start value, which may require a different traversal order.
arrow_right_alt
Exploring more efficient search algorithms for generating the sequence.
arrow_right_alt
Extending the problem to handle larger values of n (beyond 16).

help

常见问题

外企场景

继续练习

#996 平方数组的数目 #1799 N 次操作后的最大分数和 #1863 找出所有子集的异或总和再求和