Solving the Sigma-Tau Problem
2019; Association for Computing Machinery; Volume: 16; Issue: 1 Linguagem: Inglês
10.1145/3359589
ISSN1549-6333
Autores Tópico(s)Genome Rearrangement Algorithms
ResumoKnuth assigned the following open problem a difficulty rating of 48/50 in The Art of Computer Programming Volume 4A : For odd n ≥ 3, can the permutations of { 1,2,… , n } be ordered in a cyclic list so that each permutation is transformed into the next by applying either the operation σ, a rotation to the left, or τ, a transposition of the first two symbols? The Sigma-Tau problem is equivalent to finding a Hamilton cycle in the directed Cayley graph generated by σ = (1 2 ⋅ n ) and τ = (1 2). In this article, we solve the Sigma-Tau problem by providing a simple O ( n )-time successor rule to generate successive permutations of a Hamilton cycle in the aforementioned Cayley graph.
Referência(s)