# deBruijn.frink

``` /** 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]]*/ ```