De Bruijn Sequence and Universal Cycle Constructions
| Decoding UCs for Subsets and Multisets | Output | ||||||||||
|
Given a UC $\mathcal{U}$ for $k$-subsets (multisets) over a ground set of size $n$, the rank of a subset (multiset) $s$ (using a difference or frequency rep) is the starting index where $s$ appears in $\mathcal{U}$. If $s$ is a prefix of $\mathcal{U}$ then it has rank 1. If $s$ starts at the last symbol of $\mathcal{U}$ and wraps around then it has rank ${n \choose k}$. Unranking is the inverse process: given a rank $r$, it determines the subset representation $s$ that starts at index $r$ in $\mathcal{U}$.
Among the known algorithms to construct UCs for $k$-subsets and $k$-multisets, only complements of the bounded-weight Granddaddy (PCR1) have been efficiently decoded. See [GIJS26]. The bounded-weight Granddaddy, follows the Granddaddy (PCR1) concatenation construction restricted to strings meeting the specified lower bound on the weight.
For $k=3$, $n=3$, and $w=7$ we obtain the sequence $\mathcal{G}_3(3,7^\uparrow) = 133\cdot 223\cdot 233 \cdot 3$. Taking the complement of this sequence, we get $3112212111$ which is a universal cycle for $3$-subsets of $\{1,2,3,4,5\}$ using difference representatives, as illustrated in the table below.
The same sequence can be used to decode a UC for $3$-multisets over $\{0,1,2\}$ using difference representatives as illustrated in the table below.
- [GIJS26] D. Gabric, W. Imam, L. Janik-Jones, and J. Sawada. Decoding universal cycles for $t$-subsets and $t$-multisets by decoding bounded-weight de Bruijn sequences, manuscript 2026.