Title 
Constant Time and Space Updates for the SigmaTau Problem 
Authors 
Zsuzsanna Lipták, Francesco Masillo, Gonzalo Navarro, Aaron Williams 
Publication date 
2023 
Abstract 
Sawada and Williams in [SODA 2018] and [ACM Trans. Alg. 2020] gave algorithms for constructing Hamiltonian paths and cycles in the SigmaTau graph, thereby solving a problem of Nijenhuis and Wilf that had been open for over 40 years. The SigmaTau 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 leftshift (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 npermutations that is optimal in both time and space, and which lists the objects in a Gray code order using only two types of changes. 
Pages 
323330 
Conference name 
International Symposium on String Processing and Information
Retrieval 
Publisher 
SpringerVerlag (Berlin/Heidelberg, Germany) 
Reference URL 
