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:
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.
-
The postscript file (submitted version).
-
The pdf file (submitted version).
-
Latest journal version shorty.pdf.
-
The 16th Annual International Computing and Combinatorics Conference
(COCOON 2010), July 19-21, Nha Trang, Vietnam.
LNCS, 6196 (2010) 298-307.
-
Submitted February 22, 2010; accepted April 12, 2010.
-
Conference Presentation:
COCOON_UniversalPerms.pdf.
Back to list of publications.