Ranking and unranking permutations in linear time
| Author(s) : | Frank Ruskey Wendy Myrvold, |
| Publisher : | N/A |
| Publication Date : | 2001 |
| ISSN : | N/A |
| Abstract : | A ranking function for the permutations on n symbols assigns a unique integer in the range [0; n!\Gamma1] to each of the n! permutations. The corresponding unranking function is the inverse: given an integer between 0 and n!\Gamma1, the value of the function is the permutation having this rank. We present simple ranking and unranking algorithms for permutations that can be computed using O(n) arithmetic operations., |