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.


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]. Ruskey-Williams (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 300 year-old bell-ringer pattern, and the recent shift Gray code by Williams (SODA, (2009) 987-996) and are both implemented in C. For the bell-ringers algorithm, we show that the majority of changes between successive permutations are full rotations; asymptotically, the ratio of them is (n-2)/n.

Back to list of publications.