Ranking and unranking permutations in linear time (Q1603397)

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.