Shorthand Universal Cycles for Permutations

The set of permutations of <n> = {1,…,n} in one-line notation is Π(n). The shorthand encoding of a₁ ···a_n ∈ Π(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 Π(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 cdots 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 subpermutations use cool-lex order by Williams (SODA (2009) 987-996). 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 Transactions on Algorithms, Vol. 6 No. 3 Art. 45 (2010)), which we characterize here using ‘recycling’.