# 1238. Circular Permutation in Binary Representation

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).

# Solution

Approach 1: generate gray codes.

# Code (Python)

Approach 1:

    def circularPermutation(self, n: int, start: int) -> List[int]:
        # idea: generate naively.
        # n bits starts with 'start', example:
        #000
        #001
        #011
        #010
        #110
        #111
        #101
        #100
        #1100
        # basically for each extra digit, flip that digit and splice the reverse of previous results
        result = [start, start ^ 1]
        for i in range(1, n):
            # tip: flip a bit by XORing with a mask 0..010..0
            higher_bits = (result[-1] ^ (1 << i)) & ~ ((1 << i) - 1)
            for num in result[::-1]:
                result.append((num & ((1 << i) - 1)) | higher_bits)
    
        return result
    
    def circularPermutation(self, n: int, start: int) -> List[int]:
        # idea: generate gray code, then shift them
        codes = [i ^ (i >> 1) for i in range(1 << n)]
        index = codes.index(start) # find the starting point
        return codes[index: ] + codes[: index]
    
    def circularPermutation(self, n: int, start: int) -> List[int]:
        # somehow(?) shift the start 
        return [start ^ i ^ (i >> 1) for i in range(1 << n)]

Approach 2:

# Code (C++)

Approach 1:

Approach 2: