Faster Generation of Shorthand Universal Cycles for Permutations

A universal cycle for the k-permutations of <n> = {1, 2, …, n} is a circular string of length (n)_k that contains each k-permutation exactly once as a substring. Jackson (Discrete Mathematics, 149 (1996) 123–129) proved their existence for all k ≤ n − 1. Knuth (The Art of Computer Programming, Volume 4, Fascicle 2, Addison-Wesley, 2005) pointed out the importance of the k = n − 1 case, where each (n − 1)- permutation is “shorthand” for exactly one permutation of <n>. RuskeyWilliams (ACM Transactions on Algorithms, in press) answered Knuth’s request for an explicit construction of a shorthand universal cycle for permutations, and gave an algorithm that creates successive symbols in worst-case O(1)-time. This paper provides two new algorithmic constructions that create successive blocks of n symbols in O(1) amortized time within an array of length n. The constructions are based on: (a) an approach known to bell-ringers for over 300 years, and (b) the recent shift Gray code by Williams (SODA, (2009) 987-996). For (a), we show that the majority of changes between successive permutations are full rotations; asymptotically, the proportion of them is (n − 2)/n.