Name
Abstract | ||
|---|---|---|
Nijenhuis and Wilf asked the following question in their Combinatorial Algorithms textbook from 1975: Can the permutations of {1, 2,...,n} be ordered 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? Knuth rated the challenge of finding a cyclic solution for odd n (cycles do not exist for even n > 2) at 48/50 in The Art of Computer Programming, which makes it Volume 4's hardest open problem since the 'middle levels' problem was solved by Mütze. In this paper we solve the 40 year-old question by Nijenhuis and Wilf, by providing a simple successor rule to generate each successive permutation. We also present insights into how our solution can be modified to find a Hamilton cycle for odd n.
|
Year | DOI | Venue |
|---|---|---|
2018 | 10.5555/3174304.3175307 | SODA '18: Symposium on Discrete Algorithms
New Orleans
Louisiana
January, 2018 |
Field | DocType | ISBN |
Generating function,Discrete mathematics,Combinatorics,Open problem,Computer science,Successor cardinal,Hamiltonian path,Combinatorial algorithms,Permutation,Sigma,Computer programming | Conference | 978-1-61197-503-1 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joe Sawada | 1 | 66 | 9.11 |
| Aaron Williams | 2 | 139 | 20.42 |