Constant Time and Space Updates for the Sigma-Tau Problem

Zsuzsanna Lipták, Francesco Masillo, Gonzalo Navarro, and Aaron Williams

Sawada and Williams in [SODA 2018] and [ACM Trans. Alg. 2020] gave algorithms for constructing Hamiltonian paths and cycles in the Sigma-Tau graph, thereby solving a problem of Nijenhuis and Wilf that had been open for over 40 years. The Sigma-Tau graph is the directed graph whose vertex set consists of all permutations of n, and there is a directed edge from pi to pi' if pi' can be obtained from pi either by a cyclic left-shift (sigma) or by exchanging the first two entries (tau). We improve the existing algorithms from O(n) time per permutation to O(1) time per permutation. Moreover, our algorithms require only O(1) extra space. The result is the first combinatorial generation algorithm for n-permutations that is optimal in both time and space, and which lists the objects in a Gray code order using only two types of changes.