De Bruijn Sequence and Universal Cycle Constructions

For DB sequences, the underlying de Bruijn graph $H = G(n{-}1,k)$ has $k^{n-1}$ vertices and $k^n$ edges. The following tables for $k=2$ illustrate the minimum, maximum, and average ratios of the cover time to total edges by running the random generation algorithm for 10,000 iterations.

The following tables illustrate the same statistics for $k=3$ and $k=4$.

If an application does not require a sequence generated uniformly at random, an algorithm which applies a Burrows-Wheeler Transform can be applied; it outputs each DB sequence with positive probability [LP24]. The algorithm requires exponential space and has an exponential time delay to produce the first symbol with respect to the order $n$, but produces the sequence practically in $O(1)$ amortized time per symbol for $k=2$. The first estimate on the mean discrepancy of DB sequences is obtained using this algorithm [LP24].

A weight-range DB sequence is a UC for the set $\mathbf{S}_k(n,w_1,w_2)$ which contains all $k$-ary strings of length $n$ that have weight within the specified weight range $[w_1,w_2]$. The underlying graph $H$ is not necessarily regular; a random edge can be generated by applying a straightforward recurrence.

Weight range DB sequences can be constructed efficiently via cycle-joining and an $O(n)$-time successor rule when the minimum weight is 0, or the maximum weight is $(k-1)^n$ [GSWW20]. In the binary case, they can be constructed for any weight range in $O(1)$ amortized time [SWW13]. Weight range DB sequences can be applied to construct universal cycles for subsets for two different representations.

A DB sequence with forbidden $0^z$ is a maximum length UC that does not contain $0^z$ as a substring. The set $\mathbf{S}_k(n,z)$, which contains all length-$n$ strings over $\{0,1, \ldots, k{-}1\}$ that do not contain any $0^z$ as a substring or in the wraparound, admits such a UC [CEN+24]. The underlying graph $H$ is not necessarily regular; a random edge can be generated by applying a straightforward recurrence.

The lexicographically smallest DB sequences with forbidden $0^z$ can be generated via a straightforward greedy algorithm [SWW16]; it can also be generated efficiently by concatenating the aperiodic prefixes of necklaces with no $0^z$ substring as they appear in lexicographic order [SWW16,GS18]. More such sequences can be efficiently generated by applying cycle-joining [CEN+24].

For shorthand permutations, the underlying graph $H$ has $n!$ edges. Each vertex has in-degree = out-degree = 2 and thus there are $n!/2$ vertices. A random permutation can easily be generated by applying the Fisher-Yates shuffle. The following tables illustrate the minimum, maximum, and average ratios of the cover time to total edges by running the random generation algorithm for 10,000 iterations.

For $k$-subsets represented by binary strings of length $n{-}1$ with either $k$ or $k{-}1$ ones (the last bit is redundant), the underlying graph $H$ has ${n \choose k}$ edges. Multiset permutations generalize both permutations and subsets.

A random permutation, subset, or multiset permutation can easily be generated by applying the Fisher-Yates shuffle. UCs for shorthand permutations, subsets, and multiset permutations, can all be efficiently constructed.

Let $W_n$ denote the number of weak orders with $n$ competitors. The number of weak orders for $n$ competitors where there is a $k$-way tie for first is given by ${n \choose k} W_{n-k}$. Thus, $W_n = \sum_{k=1}^n {n \choose k} W_{n-k}$. This recurrence can be applied to generate a weak order uniformly at random, which is required to select the root in the arborescence. See the corresponding enumeration sequence A000670 in the Online Encyclopedia of Integer Sequences.

The following tables illustrate the minimum, maximum, and average ratios of the cover time to total edges by running the random generation algorithm for 10,000 iterations.

UCs for weak orders can be efficiently constructed.

Let $\mathbf{S}_k(n)$ denote the set of all strings corresponding to an asymmetric bracelet. A UC for $\mathbf{S}_k(n)$ is an orientable sequence with asymptotically optimal length. Consider the induced subgraph $H$ of the de Bruijn graph $G(n{-}1,k)$ where each vertex has an outgoing edge corresponding to a string in an asymmetric bracelet. The number of such edges, denoted by $S_k(n)$, has a known formula. To generate a random edge, we can randomly generate $k$-ary strings with rejection; on average only two random strings need to be generated as $n$ gets large.

The following tables illustrate the minimum, maximum, and average ratios of the cover time to total edges by running the random generation algorithm for 10,000 iterations.

Orientable sequences with asymptotically optimal length can be efficiently constructed.