Shorthand Universal Cycles for Permutations
Shorthand Universal Cycles for Permutations
复制标题
排列的速记通用循环
DOI：
10.1007/s00453-011-9544-z
复制
发表时间：
2011
期刊：
影响因子：
1.1
通讯作者：
A. Williams
中科院分区：
文献类型：
--
作者：
A. Holroyd;F. Ruskey;A. Williams
< n > ={1，…，n}的单行排列集合为Π(n)。a1⋯an∈Π(n)的简写编码为a1⋯an−1。排列的一个简写的通用循环（SP-cycle）是一个长度为n的圆串！其长度为n−1的子字符串是Π(n)的简写编码。当SP-cycle被解码时，Π(n)的阶是一个Gray码，其中连续排列的前缀旋转σi=(1 2⋯i)，对于i∈{n−1，n}。因此，sp -环可以用n！位。我们研究了具有最大和最小“权”的sp循环（Gray码中σn−1的个数）。sp循环nanb⋯nz是“周期性的”，如果它的“子排列”a,b，…，z等于Π（n−1）。证明了周期最小权值sp -环对应于(n−1)-复面体的生成树。我们提供了两个结构：B(n)和C(n)。在B(n)中，生成树使用来自钟声的“半搜索”，而在C(n)中，子排列使用Williams （SODA, 987-996, 2009）的cool-lex顺序。算法结果是：(1)B(n)和C(n)的无内存解码，(2)O（(n−1)!）(3) B(n)的二进制表示一次n位的无循环生成；(4)对B(n)的排列进行O（n+ν(n)）次排序，其中ν(n)是计算一个排列的反转向量的代价。结果(1)-(4)改进了先前的sp周期构建D(n)由Ruskey和Williams （ACM Trans.）。算法6(3):艺术。45, 2010)，我们在这里用“回收”来描述。
The set of permutations of 〈n〉={1,…,n} in one-line notation is Π(n). The shorthand encoding of a1⋯an∈Π(n) is a1⋯an−1. A shorthand universal cycle for permutations (SP-cycle) is a circular string of length n! whose substrings of length n−1 are the shorthand encodings of Π(n). When an SP-cycle is decoded, the order of Π(n) is a Gray code in which successive permutations differ by the prefix-rotation σi=(1 2 ⋯ i) for i∈{n−1,n}. Thus, SP-cycles can be represented by n! bits. We investigate SP-cycles with maximum and minimum ‘weight’ (number of σn−1s in the Gray code). An SP-cycle nanb⋯nz is ‘periodic’ if its ‘sub-permutations’ a,b,…,z equal Π(n−1). We prove that periodic min-weight SP-cycles correspond to spanning trees of the (n−1)-permutohedron. We provide two constructions: B(n) and C(n). In B(n) the spanning trees use ‘half-hunts’ from bell-ringing, and in C(n) the sub-permutations use cool-lex order by Williams (SODA, 987–996, 2009). Algorithmic results are: (1) memoryless decoding of B(n) and C(n), (2) O((n−1)!)-time generation of B(n) and C(n) using sub-permutations, (3) loopless generation of B(n)’s binary representation n bits at a time, and (4) O(n+ν(n))-time ranking of B(n)’s permutations where ν(n) is the cost of computing a permutation’s inversion vector. Results (1)–(4) improve on those for the previous SP-cycle construction D(n) by Ruskey and Williams (ACM Trans. Algorithms 6(3):Art. 45, 2010), which we characterize here using ‘recycling’.