info prev up next book cdrom email home

de Bruijn Sequence

The shortest sequence such that every string of length $n$ on the Alphabet $a$ occurs as a contiguous subrange of the sequence described by $a$. Every de Bruijn sequence corresponds to an Eulerian Cycle on a de Bruijn Graph. Surprisingly, it turns out that the lexicographic sequence of Lyndon Words of lengths Divisible by $n$ gives the lexicographically smallest de Bruijn sequence (Ruskey).


References

Ruskey, F. ``Information on Necklaces, Lyndon Words, de Bruijn Sequences.'' http://sue.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html.




© 1996-9 Eric W. Weisstein
1999-05-24