De Bruijn Sequences and Universal Cycles

Universal Cycles for Permutations

Output

Algorithm
Order $n$

Constructing universal cycles for permutations

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. 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.$

Note that 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 the latter. The following generic successor is based on the former 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$.

Generic shorthand permutation successor

$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.

Four definitions for $\mathit{inv}(\pi)$

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$ in the smallest value in an inversion $(q_i,q_j)$ in $\pi'$
$\mathit{inv}_4(\pi)$ = $q_j$ in the largest value in an inversion $(q_i,q_j)$ in $\pi'$

In the special case where $\pi'$ is the identity permutation, each function returns 0. For example, if $\pi' = 12847356$ then $\mathit{inv}_1(\pi) = 4$, $\mathit{inv}_2(\pi) = 6$, $\mathit{inv}_3(\pi) = 3$, and $\mathit{inv}_4(\pi) = 7$.

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].

Another representation for permutations also leads to a universal cycle construction [Won17].

Download source code

» C program

References

[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.

De Bruijn Sequence and Universal Cycle Constructions

Interested in generating other combinatorial objects? Visit http://combos.org