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 |

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

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

- DB constructions based on LFSR and NFSR
- Cutting down variant
- Weight range $k$-ary strings and relatives
- Information on the de Bruijn torus

More details about this project are available here.

About this project

This project was initiated in the spring of 2019. It is dedicated to presenting the many different ways de Bruijn sequences can be constructed. Additionally, universal cycle constructions for permutations, weak orders, and other combinatorial objects are also provided. Implementations of each algorithm are available to download, and an overview of each algorithm is presented.

This project was initiated in the spring of 2019. It is dedicated to presenting the many different ways de Bruijn sequences can be constructed. Additionally, universal cycle constructions for permutations, weak orders, and other combinatorial objects are also provided. Implementations of each algorithm are available to download, and an overview of each algorithm is presented.

It will be available soon via the public GIT repository