Abstract

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 $$\mathcal{O}(n)$$ time per permutation to $$\mathcal{O}(1)$$ time per permutation. Moreover, our algorithms require only $$\mathcal{O}(1)$$ extra space. The result is the first combinatorial generation algorithm for n-permutations that is optimal in both time and space, and lists the objects in a Gray code order using only two types of changes. The simple C code ($$\sim $$ 50 lines) can be found at https://github.com/fmasillo/sigma-tau. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.