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.
 A: 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.
A: How about this:
0000111101011001000|00001111...
where the bar is where it hooks back to itself.
A: 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;
} adjpair;

void backtrack(unsigned int n, unsigned int count,
               unsigned int *path, 
               unsigned char *marks, 
               adjpair *nbs, unsigned int pos)
{
  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;
  adjpair *nbs = (adjpair *)malloc(count*sizeof(adjpair));
  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);
}



