Syntactic View of Sigma-Tau Generation of Permutations

Wojciech Rytter; Wiktor Zuba

doi:10.1007/978-3-030-13435-8_33

paper

Syntactic View of Sigma-Tau Generation of Permutations

arXiv:1903.10701 · doi:10.1007/978-3-030-13435-8_33

Abstract

We give a syntactic view of the Sawada-Williams $(σ, τ)$ -generation of permutations. The corresponding sequence of $σ - τ$ -operations, of length $n! - 1$ is shown to be highly compressible: it has $O (n^{2} lo g n)$ bit description. Using this compact description we design fast algorithms for ranking and unranking permutations.

accepted on LATA2019