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