We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A New Universal Cycle for Permutations.
- Authors
Wong, Dennis
- 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.
- Subjects
PERMUTATIONS; GRAY codes; BINARY number system; CODING theory; DE Bruijn graph
- Publication
Graphs & Combinatorics, 2017, Vol 33, Issue 6, p1393
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-017-1778-3