deBruijn.frink

View or download deBruijn.frink in plain text format


/** This program generates a de Bruijn sequence.

    A de Bruijn sequence is a shortest possible sequence that contains every
    possible length-n substring, given a finite alphabet.

    For example, given the alphabet of the digits 0 and 1, a de Bruijn
    sequence of length 4 can be:
    
    0000100110101111

    which contains all the possible 4-character bitstrings 0000, 0001, 0010,
    0011, ... 1110, 1111 at some position.

    (Note that these sequences are intended to be cyclical, so the sequences
     1110, 1100, 1000 wrap around the end.)

    de Bruijn sequences are useful for data compression, finding the lowest set
    bit in an integer, and other stuff.

    References:
    http://www.1stworks.com/ref/RuskeyCombGen.pdf
    https://en.wikipedia.org/wiki/De_Bruijn_sequence

    Knuth Vol. 4
*/


/** Generate a de Bruijn sequence using the iterative FKM algorithm found
    at http://www.1stworks.com/ref/RuskeyCombGen.pdf (Algorithm 7.2)

    parameters:
      [n, alphabet] where:
         n is the length of the substrings in the sequence
         alphabet is a string containing the symbols, e.g. "01"
*/

deBruijn[n, alphabet] :=
{
   result = ""
   alphabetChars = charList[alphabet]
   k = length[alphabetChars]
   a = makeArray[[n+1], 0]

   result = result + printDeBruijn[n, 1, a, alphabetChars]
   i = n
   
   do
   {
      a@i = a@i + 1
      for j = 1 to n-i
         a@(j+i) = a@j
      
      result = result + printDeBruijn[n, i, a, alphabetChars]
      i = n
      while a@i == k -1
         i = i - 1
   } while i !=0

   return result
}

/** This method can be overloaded to print de Bruijn sequences, pre-necklaces,
    Lyndon words, or necklaces.  See the table following Algorithm 7.3 in the
    Ruskey paper.  It is currently configured to append to the de Bruijn
    sequence. 
*/

printDeBruijn[n, p, a, alphabet] :=
{
   result = ""
   if n mod p == 0
      for i = 1 to p
         result = result + alphabet@(a@i)

   return result
}

/*s = deBruijn[15, "01"]
println[s]
println["length: " + length[s]]*/


View or download deBruijn.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 17987 days, 17 hours, 33 minutes ago.