An explicit universal cycle for the (n-1)-permutations
of an n-set
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Aaron Williams,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
We show how to construct an explicit Hamilton cycle in the
directed Cayley graph Cay( { Sn, Sn-1 } : Sn ),
where Sk = (1 2 ... k).
The existence of such cycles was shown by
Jackson (Discrete Mathematics, 149 (1996) 123-129) but the
proof only shows that a certain directed graph is Eulerian, and
Knuth (Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005))
asks for an explicit construction.
We show that a simple recursion describes our Hamilton cycle and
that the cycle can be generated by an iterative algorithm that uses
O(n) space.
Moreover, the algorithm produces each successive edge of the cycle in
constant time; such algorithms are said to be loopless.
-
Appears in the ACM Transactions on Algorithms,
Volume 6, Issue 3, Article 45 (June 2010), 12 pages.
-
The postscript file.
-
The pdf file.
-
Appears on the
arXiv,
except that the appendix is omitted.
-
Submitted to ACM Transactions on Algorithms, October, 2007.
Accepted July, 2008.
-
Slides from a talk given at the Napier meeting of the New Zealand Institute
of Mathematics and its Applications, Workshop on Algorithms, February 19, 2008:
NapierTalk.pdf.
-
There is a bug in the algorithm at the end of Section 3, that could
cause it to err/crash on the final iteration.
Furthermore, there is a cleaner way to express that algorithm that
avoids the use of the directions array.
The improved algorithm may be found here:
TALGfix.pdf.
Thanks Aaron!
-
Selected citations:
-
A. Carpi, G. Fici, S. Holub, J. Oprsal and M. Sciortino,
Universal Lyndon Words, MFCS (Mathematical Foundations of Computer Science), LNCS vol. 8634, pp. 135-146, 2014.
-
Z. Wang and J. Bruck,
Partial rank modulation for flash memories,
2010 IEEE International Symposium on Information Theory (ISIT), pp. 864-868.
Back to list of publications.