De Bruijn Sequence and Universal Cycle Constructions
| Shift Rule | Output | ||||||
|
It is easy to demonstrate that universal cycles for permutations in their standard one-line notation do not exist [Joh09]. However, there are several known universal cycle constructions for permutations using a shorthand notation [RW10,HRW12,GSWW18]. Let $\pi = p_1p_2\cdots p_n$ be a permutation of order $n$. A shorthand permutation for $\pi$ is given by $\sigma = p_1p_2\cdots p_{n-1}$, where the missing symbol is $z = p_n$. Let $\mathbf{SP}(n)$ denote the set of all shorthand permutations of order $n$. For example,
$\mathbf{SP}(4) = \begin{array}{l} 123, 124, 132, 134, 142, 143, 213, 214, 231, 234, 241, 243 \\ 312, 314, 321, 324, 341, 342, 412, 413, 421, 423, 431, 432. \end{array} $
An example of a universal cycle for $\mathbf{SP}(4)$ is 123124132143243142134234.
Applying a relaxed shorthand representation for permutations also leads to a universal cycle construction [Won17].
A function $f: \mathbf{SP}(n) \rightarrow \{1,2, \ldots , n\}$ is a UC-successor for $\mathbf{SP}(n)$ if there exists a universal cycle $\mathcal{U}$ such that each $\sigma \in \mathbf{SP}(n)$ is followed by $f(\sigma)$ in $\mathcal{U}$. Observe that every UC-successor for $\mathbf{SP}(n)$ will have the form:
$f(\sigma) = \left\{ \begin{array}{ll} z &\ \ \mbox{if } \mathit{conditions}\\ p_1 \ &\ \ \mbox{otherwise.}\end{array} \right.$
The underlying feedback functions $g(\sigma) = p_1$ and $g'(\sigma) = z$ both partition the set $\mathbf{SP}(n)$ into smaller cycles. The universal cycles from [RW10,HRW12] are based on $g'$. The following generic successor is based on $g$ together with a particular inversion in each of the smaller cycles. An inversion of a permutation $\pi$ is an ordered pair ($p_i, p_j$) such that $i \lt j$ and $p_i \gt p_j$.
$f(\sigma) = \left\{ \begin{array}{ll} z &\ \ \mbox{if ($z = n$ and $p_1 = \mathit{inv}(\sigma z)$) or ($p_1 = n$ and $z = \mathit{inv}(zp_2p_3\cdots p_{n-1}p_1))$; } \\ z &\ \ \mbox{if $z \in \{p_1-1, p_1+1\}$; }\\ p_1 \ &\ \ \mbox{otherwise.}\end{array} \right.$
Each of the following definitions for $\mathit{inv}(\pi)$ will each result in a UC-successor for $\mathbf{SP}(n)$ using the above definition.
Let $\pi' = q_1q_2\cdots q_n$ be the rotation of $\pi$ starting with 1.
Using the above definitions, each UC-successor for $\mathbf{SP}(n)$ can be computed in $O(n)$ time using $O(n)$ space. The UC-successor using $inv_1$ is presented in [GSWW18].