2
$\begingroup$

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.

  • 0
    @i. m. soloveichik - A Very Big Thank You :)2012-12-27

3 Answers 3

2

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.

0

How about this: 0000111101011001000|00001111... where the bar is where it hooks back to itself.

  • 0
    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.2012-12-27
0

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  #include   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>(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<