Given 2 integers n and start. Your task is return any permutation p of (0,1,2.....,2^n -1) such that :

p[0] = start
p[i] and p[i+1] differ by only one bit in their binary representation.
p[0] and p[2^n -1] must also differ by only one bit in their binary representation.

 
Example 1:
Input: n = 2, start = 3
Output: [3,2,0,1]
Explanation: The binary representation of the permutation is (11,10,00,01). 
All the adjacent element differ by one bit. Another valid permutation is [3,1,0,2]

Example 2:
Input: n = 3, start = 2
Output: [2,6,7,5,4,0,1,3]
Explanation: The binary representation of the permutation is (010,110,111,101,100,000,001,011).

 
Constraints:

1 <= n <= 16
0 <= start < 2 ^ n

Source: leetcode | Difficulty: MEDIUM
Tags: Bit manipulation

Mathematics

Complete search

Starter code: class Solution:
    def circularPermutation(self, n: int, start: int) -> List[int]:
        

Solutions:
class Solution:

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


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		return [start ^ i ^ i >> 1 for i in range(1 << n)]


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		(res, s) = ([], None)
		for i in range(1 << n):
			tmp = i ^ i >> 1
			res.append(i ^ i >> 1)
			if tmp == start:
				s = i
		res += res
		return res[s:s + len(res) // 2]


from collections import defaultdict, deque

def gen_perm(n):
	if n == 1:
		return [0, 1]
	else:
		gen_prev = gen_perm(n - 1)
		right = [2 ** (n - 1) + num for num in gen_prev]
		return gen_prev + list(reversed(right))

class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		perm = gen_perm(n)
		i = 0
		while perm[i] != start:
			i += 1
		return perm[i:] + perm[:i]


class Solution:

	def helper(self, n):
		return n ^ n >> 1

	def circularPermutation(self, n: int, start: int) -> List[int]:
		solution = list()
		for i in range(0, 2 ** n):
			solution.append(self.helper(i))
		index = -1
		for i in range(0, len(solution)):
			if solution[i] == start:
				index = i
				break
		return solution[index:] + solution[:index]


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		gray = []
		for i in range(2 ** n):
			gray.append(i ^ i >> 1)
			if start == i ^ i >> 1:
				index = i
		return gray[index:] + gray[0:index]


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		gray = []
		for i in range(2 ** n):
			gray.append(i ^ i >> 1)
		idxStart = gray.index(start)
		result = []
		for i in range(len(gray)):
			result.append(gray[(i + idxStart) % len(gray)])
		return result


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		(gc, bit) = ([0, 1], 1)
		while bit < n:
			bit += 1
			next_vals = []
			for val in reversed(gc):
				next_vals.append(val + 2 ** (bit - 1))
			gc.extend(next_vals)
		ind = gc.index(start)
		return gc[ind:] + gc[:ind]


class Solution:

	def helper(self, n):
		if n == 1:
			return ['0', '1']
		else:
			res = self.helper(n - 1)
			return ['0' + x for x in res] + ['1' + x for x in res[::-1]]

	def circularPermutation(self, n: int, start: int) -> List[int]:
		res = [int(n, 2) for n in self.helper(n)]
		return res[res.index(start):] + res[:res.index(start)]


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		a = ['0', '1']
		for i in range(n - 1):
			a0 = ['0' + b for b in a]
			a1 = ['1' + b for b in a]
			a = a0 + a1[::-1]
		intperm = [int(b, 2) for b in a]
		idx = intperm.index(start)
		return intperm[idx:] + intperm[:idx]


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		bi = str(bin(start))[2:].zfill(n)

		def get_perm(bi_start, l):
			a = bi_start[-1 * l]
			b = str(1 - int(a))
			if l == 1:
				return [a, b]
			perms = get_perm(bi_start, l - 1)
			return [a + e for e in perms] + [b + e for e in perms[::-1]]
		return list(map(lambda x: int(x, 2), get_perm(bi, len(bi))))


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:

		def extendPerm(arr):
			arr.extend(['1' + num for num in arr[::-1]])
			for i in range(len(arr) // 2):
				arr[i] = '0' + arr[i]
		arr = ['0', '1']
		for i in range(n - 1):
			extendPerm(arr)
		nums = [int(num, 2) for num in arr]
		index = nums.index(start)
		return nums[index:] + nums[:index]


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		gray_code = [1, 0]
		for i in range(1, n):
			next_gray_code = []
			increase = 1 << i
			for num in gray_code:
				next_gray_code.append(num + increase)
			for num in reversed(gray_code):
				next_gray_code.append(num)
			gray_code = next_gray_code
		idx = gray_code.index(start)
		return gray_code[idx:] + gray_code[:idx]


class Solution:

	def circularPermutation(self, n, start):
		start = bin(start)[2:]
		while len(start) != n:
			start = '0' + start
		nums = [start]
		for i in range(n):
			tmp = []
			for j in nums[::-1]:
				if j[i] == '1':
					tmp.append(j[:i] + '0' + j[i + 1:])
				else:
					tmp.append(j[:i] + '1' + j[i + 1:])
			nums += tmp
		return [int(i, 2) for i in nums]


class Solution:

	def circularPermutation(self, n, start):

		def g(x):
			return x ^ x >> 1
		return [start ^ g(i) for i in range(1 << n)]


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		used = {start}
		two = [2 ** i for i in range(n)]
		res = [start]
		while len(res) < 2 ** n:
			i = 0
			a = res[-1] ^ two[i]
			while a in used:
				i += 1
				a = res[-1] ^ two[i]
			used.add(a)
			res.append(a)
		return res


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		return self.solve(start, n)

	def solve(self, num, length):
		if length == 1:
			if num == 1:
				return [1, 0]
			return [0, 1]
		firstnum = 1
		if num < 2 ** (length - 1):
			firstnum = 0
		res = self.solve(num - firstnum * 2 ** (length - 1), length - 1)
		ans = []
		for i in res:
			ans.append(firstnum * 2 ** (length - 1) + i)
		res.reverse()
		for i in res:
			ans.append((1 - firstnum) * 2 ** (length - 1) + i)
		return ans


from itertools import chain

class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		start_mask = start
		while start_mask:
			start_mask >>= 1
			start ^= start_mask
		out = [x ^ x >> 1 for x in chain(range(start, 2 ** n), range(start))]
		return out


class Solution:

	def grayCode(self, n: int) -> List[int]:
		if n == 0:
			return [0]
		prv_code = self.grayCode(n - 1)
		return prv_code + [2 ** (n - 1) + x for x in reversed(prv_code)]

	def circularPermutation(self, n: int, start: int) -> List[int]:
		ind = self.grayCode(n).index(start)
		return self.grayCode(n)[ind:] + self.grayCode(n)[:ind]


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		answer = [start]
		visited = set(answer)
		next = start
		while next != None:
			previous = next
			next = None
			for i in range(n):
				newNum = previous ^ 1 << i
				if newNum not in visited:
					visited.add(newNum)
					answer.append(newNum)
					next = newNum
					break
		return answer


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		perms = [2 ** i for i in range(n - 1, -1, -1)]
		end = start ^ 1
		visited = set()
		path = []

		def dfs(node):
			if node == end:
				path.append(node)
				return True
			if node in visited:
				return False
			visited.add(node)
			for perm in perms:
				if dfs(node ^ perm):
					path.append(node)
					return True
			return False
		dfs(start)
		return reversed(path)


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		used = set()
		result = [None] * int(2 ** n)
		result[0] = start
		used.add(start)
		for i in range(1, len(result)):
			for x in range(n):
				bit = bool(result[i - 1] & 1 << x)
				if bit:
					val = result[i - 1] - (1 << x)
				else:
					val = result[i - 1] + (1 << x)
				if val not in used:
					used.add(val)
					result[i] = val
					break
		return result


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		array = list(map(self.binaryToGray, range(0, 2 ** n)))
		index = array.index(start)
		return array[index:] + array[:index]

	def binaryToGray(self, n: int) -> int:
		return n ^ n >> 1


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		ans = []
		lastNumberSet = set([start ^ 1 << i for i in range(n)])
		nMax = 2 ** n
		visited = set()
		visited.add(start)

		def helper(preNum, ni):
			if ni == nMax:
				if preNum in lastNumberSet:
					return True
				return False
			for i in range(n):
				nextNum = preNum ^ 1 << i
				if nextNum not in visited:
					visited.add(nextNum)
					if helper(nextNum, ni + 1):
						ans.append(nextNum)
						return True
					visited.remove(nextNum)
			return False
		helper(start, 1)
		return [start] + ans[::-1]


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		original_list = [None for _ in range(1 << n)]
		original_list[0] = 0
		original_list[1] = 1
		for i in range(1, n):
			num_elements = 1 << i
			for j in range(num_elements):
				original_list[j] <<= 1
			for j in range(num_elements):
				original_list[num_elements + j] = original_list[num_elements - j - 1] + 1
		result_list = [None for _ in range(1 << n)]
		current = 0
		while original_list[current] != start:
			current += 1
		for i in range(1 << n):
			result_list[i] = original_list[(current + i) % (1 << n)]
		return result_list


class Solution:

	def backtracking(self, result, visited, n, found):
		if len(result) == 2 ** n:
			diff = result[-1] ^ result[0]
			i = 0
			is_one_bit = 0
			while i < n:
				if 1 << i == diff:
					is_one_bit = 1
					break
				i = i + 1
			if is_one_bit == 1:
				found[0] = 1
			return
		if found[0] == 1:
			return
		start = result[-1]
		for i in range(n):
			num = start ^ 1 << i
			if num in visited or num < 0 or num >= 2 ** n:
				continue
			result.append(num)
			visited[num] = 1
			self.backtracking(result, visited, n, found)
			if found[0] == 1:
				return
			visited.pop(num)
			result.pop()

	def circularPermutation(self, n: int, start: int) -> List[int]:
		if n == 0:
			return [0]
		result = [start]
		found = [0]
		visited = {}
		visited[start] = 1
		self.backtracking(result, visited, n, found)
		return result


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:

		def dfs(i):
			if len(p) == 1 << n:
				a = p[0] ^ p[1]
				return a and a & a - 1 == 0
			j = 1
			for _ in range(n):
				k = i ^ j
				if k not in visited:
					visited.add(k)
					p.append(k)
					if dfs(k):
						return True
					visited.remove(k)
					p.pop()
				j <<= 1
			return False
		visited = {start}
		p = [start]
		dfs(start)
		return p


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:

		def encode_as_gray(n):
			return n ^ n >> 1
		arr = [encode_as_gray(i) for i in range(0, 2 ** n)]
		i = arr.index(start)
		return arr[i:] + arr[:i]


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		gc = [0]
		for i in range(1, 2 ** n):
			gc.append(gc[-1] ^ i & -i)
		l = len(gc)
		for i in range(l):
			fe = gc[0]
			if fe == start:
				break
			else:
				gc.append(gc.pop(0))
		return gc


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		k = 1
		ans = [0, 1]
		while k <= n - 1:
			l = len(ans)
			for i in range(l - 1, -1, -1):
				ans.append(2 ** k + ans[i])
			k = k + 1
		while 1:
			if ans[0] == start:
				break
			else:
				ans.append(ans.pop(0))
		return ans


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:

		def f(n):
			if n == 0:
				return [0]
			else:
				return f(n - 1) + [2 ** (n - 1) + v for v in f(n - 1)[::-1]]
		res = f(n)
		i = res.index(start)
		return res[i:] + res[:i]


class Solution:

	def circularPermutation(self, n: int, start: int) -> List[int]:
		r = [0, 1]
		for i in range(1, n):
			r += [2 ** i + v for v in r[::-1]]
		idx = r.index(start)
		return r[idx:] + r[:idx]