Faster Generation of Shorthand Universal Cycles for Permutations

Alexander Holroyd, Microsoft Research, Redmond, Washington, USA.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
Aaron Williams, Department of Computer Science, University of Victoria, Canada.


The set of permutations of [n] = {1,2,...,n} in one-line notation is P(n). The shorthand encoding of a1 ... an in P(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 P(n). When an SP-cycle is decoded, the order of P(n) is a Gray code in which successive permutations differ by the prefix-rotation Si = (1 2 ... i) for i in {n-1, n}. Thus, SP-cycles can be represented by n! bits. We investigate SP-cycles with maximum and minimum `weight' (number of Sn-1s in the Gray code). An SP-cycle n a n b ... n z is `periodic' if its `sub-permutations' { a, b, ..., z } equal P(n). We prove that periodic min-weight SP-cycles correspond to spanning trees of the $(n{-}1)$-permutohedron. We provide two constructions: UBell(n) and UCool(n). In UBell(n) the spanning trees use `half-hunts' from bell-ringing, and in UCool(n) the sub-permutations use cool-lex order by Williams (SODA (2009) 987-996). Algorithmic results are: 1) memoryless decoding of UBell(n) and UCool(n), 2) O((n-1)!)-time generation of UBell(n) and UCool(n) using sub-permutations, 3) loopless generation of UBell(n)'s binary representation n bits at a time, and 4) O(n + u(n))-time ranking of UBell(n)'s permutations where u(n) is the cost of computing a permutation's inversion vector. Results 1)-4) improve on those for the previous SP-cycle construction UDirectn by Ruskey and Williams (ACM Transactions on Algorithms, Vol. 6 No. 3 Art. 45 (2010)), which we characterize here using `recycling'.

Keywords: Ucycles, Gray codes, Cayley graphs, permutohedron, algorithms.

Back to list of publications.