Shorthand Universal Cycles for Permutations

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.

Abstract:

The set of permutations of [n] = {1,2,...,n} in one-line notation is P(n). The shorthand encoding of a₁ ... a_n in P(n) is a₁ ... a_n-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 S_i = (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 S_n-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.

Appears in Algorithmica, 64 (2012) 215-245.
The postscript file (submitted version).
The pdf file (submitted version).
This is an extensively revised and expanded version of the paper Faster Generation of Shorthand Universal Cycles for Permutations that was presented at The 16th Annual International Computing and Combinatorics Conference (COCOON 2010), July 19-21, Nha Trang, Vietnam. LNCS, 6196 (2010) 298-307.
Submitted September 17, 2010; accepted March ???, 2011.
Aaron Williams talk slides: UniPermAppTheory.pdf. Some further results are included in these slides.
My COCOON Conference Presentation: COCOON_UniversalPerms.pdf.

Back to list of publications.