Shortened universal cycles for permutations
Shortened universal cycles for permutations
复制标题
缩短排列的通用循环
DOI：
10.1016/j.dam.2022.09.026
复制
发表时间：
2023
影响因子：
1.1
通讯作者：
Sprangel, Elizabeth
中科院分区：
文献类型：
--
作者：
Kirsch, Rachel;Lidický, Bernard;Sibley, Clare;Sprangel, Elizabeth
摘要 Kitaev 等人（2019）描述了如何通过引入不可比较的元素来缩短排列的通用词，对于任何 i∈[(n− 2)!] ，长度为 n!+ n− 1− i (n− 1) 。他们推测，对于任何 i∈[(n− 2)!]，也可以使用不可比较的元素来缩短排列的通用周期，使其长度为 n!− i (n− 1)。在这篇文章中我们证明了他们的猜想。证明是有建设性的，并且，我们还展示了一种构建排列通用循环的新方法。
Abstract Kitaev et al.(2019) described how to shorten universal words for permutations, to length n!+ n− 1− i (n− 1) for any i∈[(n− 2)!], by introducing incomparable elements. They conjectured that it is also possible to use incomparable elements to shorten universal cycles for permutations to length n!− i (n− 1) for any i∈[(n− 2)!]. In this note we prove their conjecture. The proof is constructive, and, on the way, we also show a new method for constructing universal cycles for permutations.
登录
查看更多内容
图通用循环：压缩和与通用循环的连接
DOI：
10.1016/j.aam.2023.102522
发表时间：
2022
期刊：
Adv. Appl. Math.
影响因子：
--
作者：
R. Kirsch;Clare Sibley;Elizabeth Sprangel
通讯作者：
Elizabeth Sprangel
使用离散光学传感器通过无补体 de Brujin 序列确定平面位置
DOI：
--
发表时间：
2001
期刊：
IEEE Trans. Robotics Autom.
影响因子：
--
作者：
E. Scheinerman
通讯作者：
E. Scheinerman
n 集的 (n-1) 排列的显式通用循环
DOI：
10.1145/1798596.1798598
发表时间：
2007
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
F. Ruskey;A. Williams
通讯作者：
A. Williams
影响因子：
1.1
作者：
A. Holroyd;F. Ruskey;A. Williams
通讯作者：
A. Williams
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
M. Albert;J. West
通讯作者：
J. West