Efficient universal cycle constructions for weak orders

被引：3

作者：

Sawada, Joe ^{[1
]}

Wong, Dennis ^{[2
]}

机构：

[1] Univ Guelph, Guelph, ON, Canada

[2] State Univ New York, Incheon, South Korea

来源：

DISCRETE MATHEMATICS | 2020年 / 343卷 / 10期

基金：

新加坡国家研究基金会; 加拿大自然科学与工程研究理事会;

关键词：

Weak order; Cayley permutation; Universal cycle; de Bruijn sequence; Gray code; Successor rule;

D O I：

10.1016/j.disc.2020.112022

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2020 Elsevier B.V. All rights reserved.

引用

页数：8

共 9 条

[1] LEXICOGRAPHICALLY LEAST CIRCULAR SUBSTRINGS [J].