Coollex Concatenation  Output  

Permutations and fixedweight (where the weight is the number of 1s) binary strings are special cases of strings with fixedcontent, or multiset permutations. For permutations, the content is $\{1,2,\ldots, n\}$ and for binary strings with fixedweight $w$ the content consists of $w$ 1s and $nw$ 0s. For each of these special cases, coollex order has been applied to construct universal cycles for the shorthand representations of these sets [HRW12,RSW12]. Recently, these results have been generalized for fixedcontent strings [SW21], again using a shorthand representation (ignoring the final redundant symbol of each string).
A necklace is the lexicographically smallest string in an equivalence 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 fixedcontent strings using their shorthand representation.
Concatenate together the aperiodic prefixes of the necklaces with fixedcontent as they appear in reverse coollex order.
There are iterative and recursive algorithms for generating necklaces with fixedcontent in coollex order given in [SW21]. Applying the recursive algorithm, the above universal cycle can be constructed in $O(1)$amortized time per symbol.
Observe that all 90 shorthand strings (of length 5) for original content $S$ appear exactly once in the universal cycle below.
The UC generated from this concatenation construction has a successorrule based on the Missing Symbol Resister (MSR) that can be derived by considering the first inversion in the underlying cycles [SW22].
$f(\sigma) = \left\{ \begin{array}{ll} p_1 & \ \ \mbox{if $z > p_1$ and $h(z p_1 p_2 \cdots p_{n1})$ is a necklace and $z \geq p_{n1}$;} \\ p_1 & \ \ \mbox{if $p_1 > z$ and $h(p_1 z p_2 \cdots p_{n1})$ is a necklace and $b_1 \geq p_{n1}$;} \\ z \ &\ \ \mbox{otherwise,}\end{array} \right.$
where $z$ is the missing symbol in the shorthand multiset permutation $\sigma = p_1p_2\cdots p_{n1}$ and $h(\pi)$ is the rotation of the multiset permutation $\pi = q_1q_2\cdots q_n$ that takes the longest nondecreasing suffix of $q_3\cdots q_n$ and rotates it to the front of $\pi$. For example $h(12332\color{blue}{1233}) = \color{blue}{1233}12332$.
 [HRW12] A. E. Holroyd, F. Ruskey, and A. Williams. Shorthand universal cycles for permutations. Algorithmica, 64(2):215245, 2012.
 [RSW12] F. Ruskey, J. Sawada, and A. Williams. De Bruijn sequences for fixedweight binary strings. SIAM J. Discrete Math., 26(2):605–617, 2012.
 [SW22] J. Sawada and A. Williams. Constructing the first (and coolest) fixedcontent universal cycle. Algorithmica (to appear 2022).