Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer

I think i have answer : 1000011110110010

share|improve this answer

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

share|improve this answer
    
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;
} 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);
}


share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.