De Bruijn Sequence and Universal Cycle Constructions

Shift Rule Output
Algorithm
Order $n$
Constructing universal cycles for shorthand permutations via cycle joining

It is easy to demonstrate that UCs for permutations in their standard one-line 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_{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 UC 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 UC $\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 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 cycle-joining tree rooted at $12\cdots(n-1)$ which leads to an $O(n)$-time successor rule to construct a UC for $\mathbf{SP}(n)$ [GSWW20].

Parent rule for cycle joining

Let $\sigma$ denote a non-root 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_{j-1}zp_{j+1}\cdots p_{n-1}, $$ 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 cycle-joining 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 (right-current-left) 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 UC-successor is based on $g$ together with a particular inversion in each of the smaller cycles.

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.

  1. $\mathit{inv}_1(\pi)$ = $q_j$ where $j$ is the smallest index in an inversion $(q_i,q_j)$ in $\pi'$     (corresponding to above parent rule)
  2. $\mathit{inv}_2(\pi)$ = $q_j$ where $j$ is the largest index in an inversion $(q_i,q_j)$ in $\pi'$
  3. $\mathit{inv}_3(\pi)$ = $q_j$ is the smallest value in an inversion $(q_i,q_j)$ in $\pi'$
  4. $\mathit{inv}_4(\pi)$ = $q_j$ is 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 [GSWW20].

Download source code

» C program

References

  • [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):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.

  • [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):1393-1399, November 2017.