De Bruijn Sequence and Universal Cycle Constructions

Cool-lex concatenation Output
Symbols $k$
Content ($n_1~n_2 \cdots n_k$)
Constructing universal cycles for strings with fixed-content (multiset permutations)

Permutations and fixed-weight (where the weight is the number of 1s) binary strings are special cases of strings with fixed-content, or multiset permutations. For permutations, the content is $\{1,2,\ldots, n\}$ and for binary strings with fixed-weight $w$ the content consists of $w$ 1s and $n-w$ 0s. For each of these special cases, cool-lex order has been applied to construct universal cycles for the shorthand representations of these sets [HRW12,RSW12]. Recently, these results have been generalized for fixed-content strings [SW21], again using a shorthand representation (ignoring the final redundant symbol of each string).

A necklace is the lexicographically smallest string in an equivelence class under rotation. The aperiodic prefix of a necklace $\alpha$ is the shortest string $\beta$ such that $\beta^j = \alpha$ for some integer $j$. The following is a remarkably simple, and somewhat amazing algorithm to construct a universal cycle for fixed-content strings using their shorthand representation.

Necklace Concatenation Algorithm with Cool-lex Order

Concatenate together the aperiodic prefixes of the necklaces with fixed-content as they appear in reverse cool-lex order.

There are iterative and recursive algorithms for generating necklaces with fixed-content in cool-lex order given in [SW21]. Applying the recursive algorithm, the above universal cycle can be constructed in $O(1)$-amortized time per symbol.

Example for Content $S=\{1,1,2,2,3,3\}$

Observe that all 90 shorthand strings (of length 5) for original content $S$ appear exactly once in the universal cycle below.           

Download source code

» C program

References

  • [HRW12] A. E. Holroyd, F. Ruskey, and A. Williams. Shorthand universal cycles for permutations. Algorithmica, 64(2):215-245, 2012.

  • [RSW12] F. Ruskey, J. Sawada, and A. Williams. De Bruijn sequences for fixed-weight binary strings. SIAM J. Discrete Math., 26(2):605–617, 2012.

  • [SW21] J. Sawada and A. Williams. A Universal cycle for strings with fixed-content. Manuscript, 2021.

Interested in generating other combinatorial objects? Visit http://combos.org