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:

- Euler cycles based on the de Bruijn graph
- Greedy methods
- Shift rules (binary)
- Shift rules ($k$-ary)
- Concatenation approaches

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:

- Permutations (shorthand)
- Weak orders - both height and rank representations

About this project

This project was initiated in 2019 as a spinoff off from The Combinatorial Object Server. It is dedicated to presenting the many different ways de Bruijn sequences and their relatives can be constructed. Implementations of each algorithm are available for download, and an overview of each algorithm is presented.

This project was initiated in 2019 as a spinoff off from The Combinatorial Object Server. It is dedicated to presenting the many different ways de Bruijn sequences and their relatives can be constructed. Implementations of each algorithm are available for download, and an overview of each algorithm is presented.

Contact

For comments, contributions, or corrections please contact:

Joe Sawada

jsawada@uoguelph.ca