De Bruijn Sequences

A De Bruijn sequence of order $n$ over alphabet $\{0, 1\}$ is the shortest cyclic sequence containing every $n$-bit string as a substring exactly once.

Example: For $n = 2$, the strings are $00, 01, 10, 11$. The De Bruijn sequence is $0011$ (cyclic: $00, 01, 11, 10$).

Connection to Euler circuits: Build a graph where:

• Vertices are $(n-1)$-bit strings
• Edge from $ab.c$ to $b.cd$ represents the $n$-bit string $ab.cd$

Finding an Euler circuit on this graph gives the De Bruijn sequence.