Cool-lex concatenation | Output | ||||||
|
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.
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.
Observe that all 90 shorthand strings (of length 5) for original content $S$ appear exactly once in the universal cycle below.