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

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