A universal cycle for the k-permutations of = {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 . 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) 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.
展开▼
