De Bruijn Sequence and Universal Cycle Constructions

Cut-down DB sequences

For some applications, a universal cycle of arbitrary length $1 \leq m \leq k^n$ is required such that every $k$-ary string of length $n$ appears at most once. For instance, consider trying to apply the de Bruijn Card Trick on a complete deck of 52 cards. We call such cycles cut-down de Bruijn sequences. Such universal cycles are known to exist for all $m$ and $k$ [Lem71,Yoe62], however only a few efficient constructions are known.

A cycle-joining based construction for $k=2$ can produce an exponential number of cut-down DB sequences [Etz86]. The construction can be simplified to construct a single sequence by applying PCR3-alt as the underlying feedback function to join cycles, then generalized for $k\geq 2$ to generate a single cut-down DB sequence that runs in $O(n)$ time per symbol using $O(n)$ space [CGS21]. The resulting algorithms are available for download and are used in the generation above. The cycle-joining based construction can be summarized as follows, assuming $k^{n-1} < m \leq k^n$.

By starting with the string $0^{n-1}x$, where in most cases $x=(k{-}1)$, and applying the PCR3-alt as the underlying successor, the main cycle can be constructed by cutting out cycles based on their weight and period to obtain a length that meets the bounds. The small cycle(s) can be cut out by modifying the output given by PCR3-alt for at most two strings. The choice of PCR3-alt as the underlying successor is what leads to the simplicity of this construction. By applying a suitable ranking function, this method can be employed to join specific cycles which allows for a successor-rule based approach to create the corresponding cut-down de Bruijn sequence starting from any string on the cycle.

A simple LFSR based construction, as given by Golomb [Gol17, P.193], is summarized below, assuming $m$ is not a power of 2.

This construction requires $O(n)$ space and produces the sequence in $O(n)$-amortized time per symbol. However unlike the first algorithm, this algorithm requires an exponential time delay to produce the first symbol of the sequence; a unique primitive polynomial is required for each order $n$ to obtain the feedback function; and we are unable to determine whether or not a length $n$ string is a member of the constructed cut-down de Bruijn sequence without constructing the sequence.

An LFSR approach can also be applied to construct cut-down de Bruijn sequences over an arbitrary alphabet size $k > 2$ [Lan00], though no algorithmic analysis has been done.

A generalized de Bruijn sequence is a cut-down de Bruijn sequence with length $k^{n-1} < m \leq k^n$ with an additional property: every $k$-ary string of length $n{-}1$ appears as a substring. Their existence is known for all $m$ and $k$ [GHS19]. An algorithm based on Lempel's D-morphism can be used to construct these sequences [NW21] that have an even stronger property: every $k$-ary string of length $j\leq L$ appears either $\lfloor L/k^j \rfloor$ or $\lceil L/k^j \rceil$ times as a substring. The algorithm can generate the sequence in $O(1)$-amortized time per symbol, but requires exponential space and has an exponential time delay before outputting the first symbol.