De Bruijn Sequence and Universal Cycle Constructions

Universal Cycles for Weak Orders Output
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 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 for the sizes of $\mathbf{W}(1), \mathbf{W}(2), \ldots, \mathbf{W}(6)$ are 1, 3, 13, 75, 541, and 4683 respectively.

The existence of universal cycles for $\mathbf{W}(n)$ was proved in [LG10] using the terminology ranked permutations. Using an alternate representation, existence was proved using standard graph techniques in [HH13]. The more difficult problem of efficiently constructing universal cycles for weak orders was posed in Problem 477 of [JSH09] and a construction (available for download as C program) was given in [SW19] based on the framework from [GSSW18].

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.

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

  • [SW19] J. Sawada, and D. Wong. An efficient universal cycle construction for weak orders. Submitted. 2019.