De Bruijn Sequence and Universal Cycle Constructions

Universal Cycles for Weak Orders Output
Algorithm
Order $n$
Constructing universal cycles for weak orders

A weak order is a way $n$ competitors can rank in an event, where ties are allowed. For example, the times for the 100m men's butterfly final in the 2016 Summer Olympics were:

   

The result was a three way tie for the silver medal. No bronze was awarded. This outcome corresponds to the weak ordering 82512276. Let $\mathbf{W}(n)$ denote the set of weak orders (based on this rank representation) in a competition with $n$ competitors (teams). For example, when $n=3$, the 13 different weak orders are \[ \mathbf{W}(3) = \{111, 113, 131, 311, 122, 212, 221, 123, 132, 213, 231, 312, 321\}.\] The number of weak orders of order $n$ are also known as the the ordered Bell numbers or Fubini numbers, and their enumeration sequence is A000670 in the Online Encyclopedia of Integer Sequences. The first six terms in this sequence starting at $n=1$ are 1, 3, 13, 75, 541, and 4683 respectively.

The existence of UCs for $\mathbf{W}(n)$ was proved in [LG10] using the terminology ranked permutations. For example, 1113213122123 is a UC for $\mathbf{W}(3)$. The more difficult problem of efficiently constructing UCs for weak orders was posed in Problem 477 of [JSH09]. Since $\mathbf{W}(n)$ is closed under rotation, it can be partitioned into cycles induced by the PCR. The following parent rule constructs a cycle-joining tree rooted at $1^n$ which leads to an $O(n)$-time successor rule to construct a UC for $\mathbf{W}(n)$ [SW20].

Parent rule for cycle joining

Let $\omega = w_1w_2\cdots w_n$ denote a non-root cycle representative (the lex smallest string in the cycle). Let $n(i)$ denote the number of occurrences of the symbol $i$ in $\omega$. If $\omega$ has no repeating symbols other than perhaps $1$, let $j$ denote the index of the symbol $n(1)+1$ and let $x=1$; otherwise let $j$ be the largest index containing a repeated (non-$1$) symbol and let $x = w_j + n(w_j)-1$. Then $$ \mathrm{parent}(\omega) = w_1\cdots w_{j-1}xw_{j+1}\cdots w_{n}.$$

             

The cycle-joining tree for $n=4$ (above left) can be converted to a corresponding concatenation tree (above right), which allows each symbol in the corresponding UC to be generated in $O(1)$-amortized time [SSTW23]. Outputting the aperiodic prefix (the shortest string $\beta$ such that $\omega = \beta^t$ for some $t\geq 1$) of each node $\omega$ in the concatenation tree as they appear in RCL (right-current-left) order produces the following UC for $\mathbf{W}(4)$: $$1~1114~3214~3124~2124~3114~1323~1324~13~1314~2214~2314~1133~1134~2133~2134~1222~1224~1233~1234.$$

Height representation

A weak order can be thought of as a binary relation $\preceq$ on $\Sigma = \{1, 2, \cdots, n\}$ that is transitive and complete (or connex). The latter property means that $x \preceq y$ or $y \preceq x$ (or both) for each $x,y \in \Sigma$. We write $x \equiv y$ if $x \preceq y$ and $y \preceq x$, and we write $x \prec y$ if $x \preceq y$ but $y \npreceq x$. Using this notation, a weak order can be written as a permutation where consecutive elements are separated by either $\equiv$ or $\prec$. For example, \[4 \prec 2\equiv 5 \equiv 6 \prec 3 \prec 8 \prec 7 \prec 1\] corresponds to the weak ordering from our earlier example.

The height of element $j$ is defined as the number of $\prec$ symbols that precede $j$ in the weak order. By replacing each element $j$ by its height, the weak order above can be represented by 51201143. Let $\mathbf{W_h}(n)$ denote the set of all weak orders of order $n$ using this height string representation. This is the representation used in [DG08,HH13,JSH09]. As an example, \[ \mathbf{W_h}(3) = \{000, 001, 010, 100, 011, 101, 110, 012, 120, 201, 021, 210, 102\}.\]

Since $\mathbf{W_h}(n)$ is closed under rotation, it can be partitioned into cycles induced by the PCR. Two parent rules for joining the cycles are applied in [SW20], leading to $O(n)$-time successor rules to construct UCs for $\mathbf{W_h}(n)$. The existence of such UCs was proved using standard graph techniques in [HH13].

References

  • [DG08] P. Diaconis and R. L. Graham. Products of universal cycles, in A Lifetime of Puzzles. E. Demaine, M. Demaine and T. Rodgers, eds., A K Peters/CRC Press, pages 35– 55, 2008.

  • [HH13] V. Horan and G. Hurlbert. Universal cycles for weak orders. SIAM J. Discrete Math., 27(3):1360-1371, 2013.

  • [JSH09] B. Jackson, B. Stevens, and G. Hurlbert. Research problems on Gray codes and universal cycles. Discrete Mathematics, 309(17):5341-5348, 2009.

  • [LG10] A. Leitner and A. Godbole. Universal cycles of classes of restricted words. Discrete Mathematics, 310(23):3303-3309, 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.

  • [SW20] J. Sawada and D. Wong. Efficient universal cycle constructions for weak orders. Discrete Mathematics, 343(10):112022, 2020.