Constant Time and Space Updates for the Sigma-Tau Problem

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 di- rected graph whose vertex set consists of all permutations of n, and there is a directed edge from π to π′ if π′ can be obtained from π 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.