Construct a circle contains all n-bit binary number

Question

The problem comes from an interview: How to construct a circle (01 round sequences with length 2^n) contains all possible n-bit binary number, each number appears once and only once. For example, when n=2, the result is:

0--0
|  |
1--1

the numbers are {00, 01, 11, 10}. All possible numbers appear once and only once. When n=3, here is an example answer:

  0--0--1
 /       \
0         1
 \       /  
  1--0--1

Answer 1

Linear Shift Feedback Registers come handy in generating this sequence:

Starting with 001, generate the 7 next bits using LSFR with polynomial p(x) = 101. The sequence would be '001 1101 001'. (The period of LSFR is 2^N - 1, with the all-zero entry missing.)

Noticing that the same 3-bit sequence occurs in both ends, we'll replace the last sequence with a zero -- '00111010'.

The offsets where the numbers 0..7 occur are 7, 0, 5, 1, 6, 4, 3, 2.

The polynomial is applied by xoring all the bits of the previous N-bit entry where the polynomial has a one.

    0 0 1
xor 1 0 1 => (0 and 1) xor (0 and 0) xor (1 and 1) => 1

    0 0 1 1
xor   1 0 1 ==> (0 and 1) xor (1 and 0) xor (1 and 1) => 1

As a generic rule, the polynomial has a 1 on both ends, and some number of ones in the middle; one can try to brute force search the missing bits or google for "primitive polynomials in galois field" for a comprehensive list.

Answer 2

You need to construct binary de Bruijn cycle. Wikipedia article suggests several ways to do it:

The De Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional De Bruijn graph over k symbols (or equivalently, a Eulerian cycle of a (n − 1)-dimensional De Bruijn graph).

An alternative construction involves concatenating together, in lexicographic order, all the Lyndon words whose length divides n.

De Bruijn sequences can also be constructed using shift registers or via finite fields.