De Bruijn Sequence and Universal Cycle Constructions

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   0100 1001 0011 0111 1111 1110 1100 1000

• 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.