# Consider the sequence 01110100…

Consider the sequence 01110100 as being arranged in a circular pattern. Notice that every one of the eight possible binary triples: 000, 001, 011, . . . , 111 appear exactly once in the circular list. Can you construct a similar list of length 16 where all the four binary digit patterns appear exactly once each?

Any ideas would be greatly appreciated. Thank's.

-
Can you answer the first part of the question yourself? It just means writing out a list... – Thomas Andrews Dec 27 '12 at 13:57
Induction?[filler] – akkkk Dec 27 '12 at 14:00
Look for DeBruijn sequences or Huffman code. – i. m. soloveichik Dec 27 '12 at 14:01
@Thomas Andrews - yes, for the sequence 01110100 I've build already the list/table, but can't find a way how to construct a similar list of length 16... – DiscreteMath'sFan Dec 27 '12 at 14:02
@i. m. soloveichik - A Very Big Thank You :) – DiscreteMath'sFan Dec 27 '12 at 14:08

This is called a De Bruijn sequence. Your example contains all possible 3-tuples of 2 symbols. De Bruijn sequences exist which contain all possible $n$-tuples of $k$ symbols.

-

I think i have answer : 1000011110110010

-

-
Just looked up MJD link to DeBruijn. Seems there are lots, and the one Nikola gave is a bit different from that in my answer. – coffeemath Dec 27 '12 at 14:31

The following extremely straightforward C program can perhaps provide some insight into how these sequences are constructed. It first constructs the graph $G$ on $2^n$ vertices (the pattern is $n$ bits wide) of all possible patterns with a forward edge between two vertices $u$ and $v$ if the lower $n-1$ bits of $u$ match the upper $n-1$ bits of $v.$ Next the program builds Hamiltonian paths of $G$ and whenever it finds one, the sequence of nodes and of bits is displayed. Not difficult to adapt to different pattern sizes and alphabets. Compile with GCC and run from the command line with a single argument ($n$).

#include <stdio.h>
#include <stdlib.h>

typedef struct{
unsigned int nb0, nb1;

void backtrack(unsigned int n, unsigned int count,
unsigned int *path,
unsigned char *marks,
{
unsigned int m;

if(pos==count-1){
for(m=0; m<count; m++){
printf("%d ", path[m]);
}

for(m=0; m<count; m++){
printf("%c", ((path[m])>>(n-1))>0 ? '1' : '0');
}

printf("\n");

return;
}

unsigned int cur = path[pos];
if(!(marks[nbs[cur].nb0])){
path[pos+1] = nbs[cur].nb0;

marks[nbs[cur].nb0] = 1;
backtrack(n, count, path, marks, nbs, pos+1);
marks[nbs[cur].nb0] = 0;
}
if(!(marks[nbs[cur].nb1])){
path[pos+1] = nbs[cur].nb1;

marks[nbs[cur].nb1] = 1;
backtrack(n, count, path, marks, nbs, pos+1);
marks[nbs[cur].nb1] = 0;
}
}

int main(int argc, char **argv){
unsigned int n;

if(argc!=2 || sscanf(argv[1], "%u", &n)!=1 ||
n<1 || n>=256){
fprintf(stderr, "positive integer expected\n");
exit(-1);
}

unsigned int count = 1<<n;
if(nbs == NULL){
fprintf(stderr, "first malloc failed\n");
exit(-2);
}

unsigned char *marks =
(unsigned char *)malloc(count*sizeof(unsigned char));
if(marks == NULL){
fprintf(stderr, "second malloc failed\n");
exit(-3);
}

unsigned int *path =
(unsigned int *)malloc(count*sizeof(unsigned int));
if(path == NULL){
fprintf(stderr, "third malloc failed\n");
exit(-4);
}

unsigned int m;
for(m=0; m<count; m++){
marks[m] = 0;
}

for(m=0; m<count; m++){
nbs[m].nb0 = (m & ((1<<(n-1))-1))<<1;
nbs[m].nb1 = nbs[m].nb0+1;
}

marks[0] = 1; path[0] = 0;
backtrack(n, count, path, marks, nbs, 0);

free(nbs);
free(marks);
free(path);

exit(0);
}


-