A new universal cycle for permutations (Q1696522)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A new universal cycle for permutations
scientific article

    Statements

    A new universal cycle for permutations (English)
    0 references
    0 references
    14 February 2018
    0 references
    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.
    0 references
    0 references
    universal cycles
    0 references
    permutations
    0 references
    de Bruijn sequences
    0 references
    Gray codes
    0 references

    Identifiers