Abstract | ||
---|---|---|
We give a syntactic view of the Sawada-Williams (sigma, tau) -generation of permutations. The corresponding sequence Seq(n) of sigma tau-operations of length n! - 1 is shown to have a compact description of size Theta(n(2)) in terms of straight-line programs. Using the compact description, we design almost linear time ranking and unranking algorithms. (C) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1016/j.tcs.2021.06.008 | THEORETICAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
Sigma-tau generation, Permutations, Straight-line program, Ranking | Journal | 882 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
wojciech rytter | 1 | 130 | 17.13 |
Wiktor Zuba | 2 | 0 | 1.69 |