De Bruijn Sequence and Universal Cycle Constructions

Given an alphabet of size $k$, a de Bruijn (DB) sequence of order $n$ is a cyclic 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
  0100 1001 0011 0111 1111 1110 1100 1000

The 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
  • Successor (shift) rules based on cycle joining
  • Concatenation approaches
Additionally, there is an algorithm to decode the lexicographically smallest DB sequence (the Granddaddy) and a section on properties including an analysis of DB sequence discrepancies. For a deeper theoretical background on DB sequences, see the recent 2024 book by Etzion: Sequences and the de Bruijn Graph.

More generally, a universal cycle of order $n$ for a set $\mathbf{S}$ of length $n$ strings is a cyclic 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)
  • Subsets (shorthand binary, difference, standard representations)
  • Weak orders - both height and rank representations
  • Cut-down DB sequences
  • Orientable sequences
Cite this project as: De Bruijn Sequence and Universal Cycle Constructions (2024). http://debruijnsequence.org.
About this project

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 Sep 20, 2024

Contributors

Daniel Gabric

Aysu Gündoǧan

Luke Janik-Jones

Zsuzsa Lipták

Josh McCaskill

Torsten Mütze

Luca Parmigiani

Evan Sala

Joe Sawada

Jack Sears

Andrew Trautrim

Aaron Williams

Dennis Wong

For comments, contributions, or corrections please contact:

Joe Sawada
jsawada@uoguelph.ca