Name
Abstract | ||
|---|---|---|
Knuth 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.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1145/3359589 | ACM Transactions on Algorithms (TALG) |
Keywords | Field | DocType |
Cayley graph, Hamilton cycle, Sigma-tau problem, permutations, successor rule | Discrete mathematics,Algebra,Sigma,Mathematics | Journal |
Volume | Issue | ISSN |
16 | 1 | 1549-6325 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joe Sawada | 1 | 66 | 9.11 |
| Aaron Williams | 2 | 139 | 20.42 |