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 40 years. The following different construction methods are presented:
- Euler cycles based on the de Bruijn graph
- Linear feedback shift registers (LFSRs)
- Recursive methods
- Greedy methods
- Shift rules based on cycle joining
- Concatenation approaches
More generally, a universal cycle of order $n$ 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)
- Multiset permutations (strings with fixed content)
- Weak orders - both height and rank representations
- Orientable sequences
This project was initiated as a spinoff 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 the algorithms are available for download.
Last updated Mar 14, 2023
Daniel Gabric
Aysu Gündoǧan
Torsten Mütze
Evan Sala
Joe Sawada
Aaron Williams
Dennis Wong
For comments, contributions, or corrections please contact:
Joe Sawada
jsawada@uoguelph.ca