###
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.