Ranking and unranking permutations in linear time

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 simp...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2001-09, Vol.79 (6), p.281-284
Main Authors: Myrvold, Wendy, Ruskey, Frank
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Classical combinatorial problems
Combinatorial problems
Combinatorics
Combinatorics. Ordered structures
Computer programming
Exact sciences and technology
Linear programming
Mathematical models
Mathematical programming
Mathematics
Operational research and scientific management
Operational research. Management science
Permutation
Ranking
Sciences and techniques of general use
Studies
Unranking
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0020-0190
1872-6119
DOI:10.1016/S0020-0190(01)00141-7