De Bruijn Sequence and Universal Cycle Constructions
| Decoding UCs for Shorthand Permutations | Output | ||||||||
|
Decoding (ranking/unranking) the Direct and Bell-ringer UCs for Shorthand Permutations
Given a UC $\mathcal{U}$ for shorthand permutations of order $n$, the rank of a shorthand permutation $\pi$ (of length $n-1$) is the starting index where $\pi$ appears in $\mathcal{U}$. If $\pi$ is a prefix of $\mathcal{U}$ then it has rank 1. If $\pi$ starts at the last symbol of $\mathcal{U}$ and wraps around then it has rank $n!$. Unranking is the process of determining the string $\pi$ in $\mathcal{U}$ starting at index $r$ (the rank of $\pi$).
Example
Both the Direct and Bell-ringer UC have known concatenation constructions. By understanding the ordering of the permutations as they are concatenated allows for the corresponding sequences to be efficiently decoded [RW10,HRW12].
Consider the Direct UC for shorthand permutations for $n=4$:
432142134132431241234231.
The shorthand permutation $\pi = 134$ has rank 7.
References
- [HRW12] A. E. Holroyd, F. Ruskey, and A. Williams. Shorthand universal cycles for permutations. Algorithmica, 64(2):215-245, 2012.
- [RW10] F. Ruskey and A. Williams. An explicit universal cycle for the ($n$-1)-permutations of an $n$-set. ACM Transactions on Algorithms (TALG), 6(3):1-12, 2010.