A New Universal Cycle for Permutations

作者：Wong, Dennis^*

来源：Graphs and Combinatorics, 2017, 33(6): 1393-1399.

DOI：10.1007/s00373-017-1778-3

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

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.

• 出版日期2017-11