Ranking and unranking permutations in linear time (Q1603397)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Ranking and unranking permutations in linear time |
scientific article; zbMATH DE number 1767194
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Ranking and unranking permutations in linear time |
scientific article; zbMATH DE number 1767194 |
Statements
Ranking and unranking permutations in linear time (English)
0 references
14 July 2002
0 references
A ranking function for the permutations on \(n\) symbols assigns a unique integer in the range [0,n!-1]\ to each of the \(n!\) permutations. The corresponding unranking function is the inverse: given an integer between \(0\) and \(n!-1\), 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.
0 references
Permutation
0 references
Ranking
0 references
Unranking
0 references
Algorithms
0 references
Combinatorial problems
0 references
0 references
