A De Bruijn sequence of order over alphabet is the shortest cyclic sequence containing every -bit string as a substring exactly once.
Example: For , the strings are . The De Bruijn sequence is (cyclic: ).
Connection to Euler circuits: Build a graph where:
- Vertices are -bit strings
- Edge from to represents the -bit string
Finding an Euler circuit on this graph gives the De Bruijn sequence.