Given an alphabet of size $k$, a de Bruijn (DB) sequence of order $n$ is a circular string of length $k^n$ where every $k$-ary string of length $n$ appears exactly once as a substring.
Example $n=4$ and $k=2$ 0000101101001111 is a DB sequence where the 16 unique substrings of length 4 visited in order are:
0000 0001 0010 0101 1011 0110 1101 1010 |
![]() |
This inspiration for this project is to update Fredricksen's survey [SIAM Review, Vol 24 (1982)] to include new results and constructions from the past 35+ years. The following different construction methods are presented:
More generally, a universal cycle for a set $\mathbf{S}$ of length $n$ strings, is a circular string of length $|\mathbf{S}|$ where every string in $\mathbf{S}$ appears exactly once as a substring. Universal cycle constructions are provided for:
For comments, contributions, or corrections please contact:
Joe Sawada
jsawada@uoguelph.ca