Abstract
We introduce a novel notation, the relaxed shorthand notation, to encode permutations. We then present a simple shift rule that exhaustively lists out each of the permutations exactly once. The shift rule induces a cyclic Gray code for permutations where successive strings differ by a rotation or a shift. By concatenating the first symbol of each string in the listing, we produce a universal cycle for permutations in relaxed shorthand notation. We also prove that the universal cycle can be constructed in O(1)-amortized time per symbol using O(n) space.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Chung, F., Diaconis, P., Graham, R.: Universal cycles for combinatorial structures. Discret. Math. 110(1–3), 43–59 (1992)
Holroyd, A., Ruskey, F., Williams, A.: Faster generation of shorthand universal cycles for permutations. In: Computing and combinatorics, 16th annual international conference, COCOON 2010, Nha Trang, Vietnam, July 19–21, 2010. Proceedings, pp. 298–307 (2010)
Holroyd, A., Ruskey, F., Williams, A.: Shorthand universal cycles for permutations. Algorithmica 64(2), 215–245 (2012)
Jackson, B.: Universal cycles of \(k\)-subsets and \(k\)-permutations. Discret. Math. 117(13), 141–150 (1993)
Johnson, R.: Universal cycles for permutations. Discret. Math. 309(17), 5264–5270 (2009)
Knuth, D.: The art of computer programming. Volume 4, fascicule 2. , Generating all tuples and permutations. The art of computer programming. Addison-Wesley, Upper Saddle River (2005) (Autre tirage: (2010))
Ruskey, F., Williams, A.: An explicit universal cycle for the (n-1)-permutations of an n-set. ACM Trans. Algor. 6(3) , 45:1–45:12 (2010). doi:10.1145/1798596.1798598
Williams, A.: Loopless generation of multiset permutations using a constant number of variables by prefix shifts. In: Proceedings of the twentieth annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4–6, 2009, pp. 987–996 (2009)
Acknowledgements
The author would like to thank Joe Sawada and Aaron Williams for their helpful advice that greatly improved this paper.
Author information
Authors and Affiliations
Corresponding author
Appendix: C code to Generate a Relaxed Shorthand Universal Cycle for Permutations in \({\varPi }({n})\) in O(1)-Amortized Time per Symbol Using O(n) Space
Appendix: C code to Generate a Relaxed Shorthand Universal Cycle for Permutations in \({\varPi }({n})\) in O(1)-Amortized Time per Symbol Using O(n) Space
Rights and permissions
About this article
Cite this article
Wong, D. A New Universal Cycle for Permutations. Graphs and Combinatorics 33, 1393–1399 (2017). https://doi.org/10.1007/s00373-017-1778-3
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-017-1778-3