A new universal cycle for permutations
In this nice note, the author presents a simple 4-case shift rule on the set of permutations \(\Pi(n)\) of \(\{1,\ldots,n\}\) that is then proved to iteratively produce each of these \(n!\) permutations in cyclical order. The author then considers the sequence \(U\) obtained by successively choosing the first symbol of each of these permutations, starting with the permutation \(12\cdots n\). Using shorthand notation \(a_1a_2\cdots a_{n-1}\) to represent permutations \(a_1a_2\cdots a_n\in \Pi(n)\), it is possible to express each of the permutations in \(\Pi(n)\) as \(n!\) consecutive subsequences of length \(n-1\) of some cyclic sequence of \(n!\) symbols from \(\{1,2,\ldots,n\}\). The author introduce relaxed shorthand notation which cleverly generalises shorthand notation for permutations, and proves that the consecutive subsequences of length \(n\) in the sequence \(U\), taken cyclicly, uniquely represents each of the permutations in \(\Pi(n)\) via this relaxed shorthand notation. An efficient algorithm to generate \(U\) is also given, along with C code to implement this algorithm.
- An explicit universal cycle for the (n-1)-permutations of an n-set
- Faster generation of shorthand universal cycles for permutations
- scientific article; zbMATH DE number 7051269 (Why is no real title available?)
- scientific article; zbMATH DE number 2176112 (Why is no real title available?)
- Shorthand universal cycles for permutations
- Universal cycles for combinatorial structures
- Universal cycles for permutations
- Universal cycles of k-subsets and k-permutations
- Shorthand universal cycles for permutations
- A cycle lemma for permutation inversions
- Shortened universal cycles for permutations
- Enumerations of universal cycles for \(k\)-permutations
- scientific article; zbMATH DE number 1811347 (Why is no real title available?)
- Faster generation of shorthand universal cycles for permutations
- Efficient enumeration of cyclic permutations in situ
- On a greedy algorithm to construct universal cycles for permutations
- Constructing the first (and coolest) fixed-content universal cycle
- An explicit universal cycle for the (n-1)-permutations of an n-set
- An effective approach to enumerate universal cycles for k-permutations
- Efficient methods of constructing universal cycles for k-permutations
- Efficient universal cycle constructions for k-permutations via concatenation trees
This page was built for publication: A new universal cycle for permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1696522)
