An explicit universal cycle for the (n-1)-permutations of an n-set
An explicit universal cycle for the (n-1)-permutations of an n-set
复制标题
n 集的 (n-1) 排列的显式通用循环
DOI：
10.1145/1798596.1798598
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
A. Williams
中科院分区：
文献类型：
--
作者：
F. Ruskey;A. Williams
给出了如何在有向Cayley图（{σ<sub><i>n</i></sub>，σ<sub><i>n</i>−1</sub>}：<sub><i>Sn</i></sub>）中构造一个<i>显式</i>汉密尔顿圈，其中σ<sub><i>k</i></sub>为旋转（1 2<i>k</i>）.杰克逊[1996]证明了这种圈的存在性，但证明仅表明某个有向图是欧拉图，Knuth [2005]要求明确的构造。我们表明，一个简单的递归描述我们的汉密尔顿周期和周期可以产生的迭代算法，使用<i>O</i>（<i>n</i>）空间。此外，该算法在恒定时间内产生周期的每个连续边沿;这种算法被称为<i>无环</i>算法。最后，我们的汉密尔顿圈可以用来构造一<i>个n</i>-集合的（<i>n</i>-1）-置换的显式泛圈，或者作为一个有效算法的基础，用于在循环数组或链表中生成<i>n</i>-集合的每个<i>n</i>-置换。
We show how to construct an <i>explicit</i> Hamilton cycle in the directed Cayley graph &Cayrarr;({σ<sub><i>n</i></sub>, σ<sub><i>n</i>−1</sub>}: S<sub><i>n</i></sub>), where σ<sub><i>k</i></sub> is the rotation (1 2 &cdots; <i>k</i>). The existence of such cycles was shown by Jackson [1996] but the proof only shows that a certain directed graph is Eulerian, and Knuth [2005] asks for an explicit construction. We show that a simple recursion describes our Hamilton cycle and that the cycle can be generated by an iterative algorithm that uses <i>O</i>(<i>n</i>) space. Moreover, the algorithm produces each successive edge of the cycle in constant time; such algorithms are said to be <i>loopless</i>. Finally, our Hamilton cycle can be used to construct an explicit universal cycle for the (<i>n</i>−1)-permutations of a <i>n</i>-set, or as the basis of an efficient algorithm for generating every <i>n</i>-permutation of an <i>n</i>-set within a circular array or linked list.