Efficient universal cycle constructions for weak orders

A weak order is a way n competitors can rank in an event, where ties are allowed. A weak order can also be thought of as a relation on {1,2,…,n} that is transitive and complete. We provide the first efficient algorithms to construct universal cycles for weak orders by considering both rank and height representations. Each algorithm constructs the universal cycles in O(n) time per symbol using O(n) space.