Shift Rule  Output  

It is easy to demonstrate that UCs for permutations in their standard oneline notation do not exist [Joh09]. However, there are several known UC 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_{n1}$, 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 UC for $\mathbf{SP}(4)$ is 123124132143243142134234.
A function $f: \mathbf{SP}(n) \rightarrow \{1,2, \ldots , n\}$ is a UCsuccessor for $\mathbf{SP}(n)$ if there exists a UC $\mathcal{U}$ such that each $\sigma \in \mathbf{SP}(n)$ is followed by $f(\sigma)$ in $\mathcal{U}$. Observe that every UCsuccessor 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 UCs from [RW10,HRW12] are based on $g'$. The function $g$ is the feedback function for the PCR; it partitions $\mathbf{SP}(n)$ into cycles corresponding to the necklaces. The following parent rule constructs a cyclejoining tree rooted at $12\cdots(n1)$ which leads to an $O(n)$time successor rule to construct a UC for $\mathbf{SP}(n)$ [GSWW20].
Let $\sigma$ denote a nonroot cycle representative (the lex smallest string in the cycle) where $z$ is the missing symbol. If $z = n$, let $j$ denote the smallest index such that there exists an inversion $(p_i,p_j)$ for some $i\lt j$; otherwise let $j$ denote the index of $z+1$. Then $$ \mathrm{parent}(\sigma) = p_1\cdots p_{j1}zp_{j+1}\cdots p_{n1}, $$ where an inversion of a $\sigma$ is an ordered pair ($p_i, p_j$) such that $i \lt j$ and $p_i \gt p_j$.
The cyclejoining tree for $n=4$ based on the above parent rule has the same representatives as the corresponding concatenation tree above. Visiting each node in the concatenation tree as they appear in RCL (rightcurrentleft) order produces the following UC for $\mathbf{SP}(4)$: $$1234~1235~1243~1254~1325~1435~2435~1425~1324~1354~2354~1253~1245~1342~1352$$ $$1432~1543~2543~1542~1532~1453~2453~1423~1524~1534~2534~1523~1452~1345~2345.$$ It can be generated in $O(1)$amortized time per symbol [SSTW23].
Applying a relaxed shorthand representation for permutations also leads to a UC construction [Won17].
Shift rules
The following generic UCsuccessor is based on $g$ together with a particular inversion in each of the smaller cycles.
$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_{n1}p_1))$; } \\ z &\ \ \mbox{if $z \in \{p_11, p_1+1\}$; }\\ p_1 \ &\ \ \mbox{otherwise.}\end{array} \right.$
Each of the following definitions for $\mathit{inv}(\pi)$ will each result in a UCsuccessor 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'$ (corresponding to the above parent rule)
 $\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 UCsuccessor for $\mathbf{SP}(n)$ can be computed in $O(n)$ time using $O(n)$ space. The UCsuccessor using $inv_1$ is presented in [GSWW20].
 [GSWW20] D. Gabric, J. Sawada, A. Williams, and D. Wong. A successor rule framework for constructing $k$ary de Bruijn sequences and universal cycles. IEEE Transactions on Information Theory, 66(1):679–687, 2020.
 [HRW12] A. E. Holroyd, F. Ruskey, and A. Williams. Shorthand universal cycles for permutations. Algorithmica, 64(2):215245, 2012.
 [JSH09] B. Jackson, B. Stevens, and G. Hurlbert. Research problems on Gray codes and universal cycles. Discrete Mathematics, 309(17):53415348, 2009.
 [Joh09] J. R. Johnson. Universal cycles for permutations. Discrete Mathematics, 309(17):52645270, 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):112, 2010.
 [SSTW23] J. Sawada, J. Sears, A. Trautrim, and A. Williams. Concatenation trees: A framework for efficient universal cycle and de Bruijn sequence constructions. arXiv preprint arXiv:2308.12405, 2023.
 [Won17] D. Wong. A new universal cycle for permutations. Graph. Comb., 33(6):13931399, November 2017.