A New Universal Cycle for Permutations

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)1393-1399
Number of pages7
JournalGraphs and Combinatorics
Issue number6
Publication statusPublished - 1 Nov 2017
Externally publishedYes


  • Gray codes
  • Permutations
  • Universal cycles
  • de Bruijn sequences


Dive into the research topics of 'A New Universal Cycle for Permutations'. Together they form a unique fingerprint.

Cite this