A beautiful arrangement....

During the lunch yesterday, Prof. Julio mentioned me about a pattern of positives and negatives in social groups. I was then reminded of a puzzle asked by Manjul Bhargava that whether it is possible to arrange binary numbers such that every 3-letter block is different.
It is a beautiful arrangement of symbols as we see below.

0001011100

If we group every three adjacent letters, we get different numbers.
They are:

0001011100

0001011100

0001011100

0001011100

0001011100

0001011100

0001011100

0001011100

Interestingly, their decimal equivalents are 0, 1, 2, 5, 3, 7, 6, 4. 

Is this the only pattern?

Do you observe any other beautiful element in this pattern?
Look at the things vertically.
You see first a block of 0's, then 1, then 0, then 1's and then 0's.

0001011100

0001011100

0001011100

0001011100

0001011100

0001011100

00  01011100

00  01011100

00  01011100

1100

0001011100

0001011100

0001011100

0001011100

0001011100

and

0001011100

0001011100

Julio's social groups are people who are  + and -, replacing 1and 0, respectively.
We represent the structure as:

---+-+++--

Can we extend this to block of four letters?
Answer is yes. Look at the following pattern. It is provided by Lavina D'Souza.

0000100111101011000

Their decimal equivalents are 0,1,2,4,9,3,7,15,14,13,10,5,11,6,12,8.
They are all the elements of Z16.

It's a good turnout.

Is there a pattern for blocks of n letters?

We begin with block of length 2. Strange though, there four different patterns! We use binary tree to construct them.
Algorithm:

1. Begin with any binary number of length 2.
2. Remove the bit on the left
3. Add 0, 1 to form the new binary number that is not already an ancestor.
4. Repeat steps 2 and 3
5. Stop when all the four binary numbers are found.

See the diagram given below for more details.

This can be expressed and explained with the help a directed graph (digraph).  A directed graph is a graph with edges having directions. If there are no specific direction for an edge, then it is assumed to be bidirectional.

The diagrams given below are the same. One is with directed edges and the other is with undirected edge. Both of them represent the binary number 10. This gives all possible binary numbers of length 1. Every consecutive block of length one gives distinct binary numbers of length 1. Of course, it is very obvious!

We now move to binary numbers of length two. We have seen this. Neverthless, the following digraph gives all the possible smallest binary numbers whose every consecutive two bits give distinct all the distinct binary numbers of length two.

How do we get all the possible smallest binary numbers whose every consecutive two bits give distinct all the distinct binary numbers of length two? It is quite simple. Start with any vertex. Follow the directions. Visit every vertex in the graph.
As an example, we begin with the the top vertex 10. Following the directions, we choose 00, 01 and then 11.  Removing the common bits, we get 10011.
In fact, what we find is a Hamiltonian Path in the directed graph.
A Hamiltonian Path is a path in a graph with each vertex appearing exactly once.

It will be quite interesting and every effective in the case of binary numbers of length three.
See that diagram below.

We can begin from any vertex. Every Hamiltonian Path gives the smallest binary number whose every consecutive three bits give all a distinct binary number whose decimal equivalent is in the set Z8={0,1,2,3,4,5,6,7}.

When it comes to binary numbers of length four, every Hamiltonian Path in the following diagram gives the solution.

One such path is given here. Follow through the red edges.

The binary number equivalent of this is

0000100111101011000

This is an interesting sequence. It is not just linear, it is cyclic as well. Any four consecutive bits give a unique number from the set Z16={0,1,2,3,4,5,6,7,8,9,10,11,12,1,3,14,15}. See the diagram below.