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