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).


Ruskey, F. ``Information on Necklaces, Lyndon Words, de Bruijn Sequences.''

© 1996-9 Eric W. Weisstein