##
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*_{1} ... *a*_{n} in **P**(*n*) is
*a*_{1} ... *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-1}s
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 UDirect*n* 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.