A Universal Cycle for Strings with Fixed-Content (Which Are Also Known as Multiset Permutations)

We develop the first universal cycle construction for strings with fixed-content (also known as multiset permutations) using shorthand representation. The construction runs a necklace concatenation algorithm on cool-lex order for fixed-content strings, and is implemented to generate the universal cycle in amortized O(1)-time per symbol. This generalizes two previous results: a universal cycle for shorthand permutations by Ruskey, Holroyd, and Williams [Algorithmica 64 (2012)] and a universal cycle for shorthand fixed-weight binary strings by Ruskey, Sawada, and Williams [SIAM J. on Disc. Math. 26 (2012)]. A consequence of our construction is the first shift Gray code for fixed-content necklaces.