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].
Shift rules
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.
- $\mathit{inv}_1(\pi)$ = $q_j$ where $j$ is the smallest index in an inversion $(q_i,q_j)$ in $\pi'$
- $\mathit{inv}_2(\pi)$ = $q_j$ where $j$ is the largest index in an inversion $(q_i,q_j)$ in $\pi'$
- $\mathit{inv}_3(\pi)$ = $q_j$ is the smallest value in an inversion $(q_i,q_j)$ in $\pi'$
- $\mathit{inv}_4(\pi)$ = $q_j$ is the largest value in an inversion $(q_i,q_j)$ in $\pi'$
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].
- [GSWW18] D. Gabric, J. Sawada, A. Williams, and D. Wong. A successor rule framework for constructing de Bruijn sequences and universal cycles. Submitted, 2018.
- [HRW12] A. E. Holroyd, F. Ruskey, and A. Williams. Shorthand universal cycles for permutations. Algorithmica, 64(2):215-245, 2012.
- [JSH09] B. Jackson, B. Stevens, and G. Hurlbert. Research problems on Gray codes and universal cycles. Discrete Mathematics, 309(17):5341-5348, 2009.
- [Joh09] J. R. Johnson. Universal cycles for permutations. Discrete Mathematics, 309(17):5264-5270, 2009.
- [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.
- [Won17] D. Wong. A new universal cycle for permutations. Graph. Comb., 33(6):1393-1399, November 2017.