How can I sort permutations of numbers {1, 2, ..., M}, so then I can provide rank()* and unrank()** in O(M) time?

*rank(P) function of a permutation P tells at which index permutation P is located.

**The inverse function to rank(P) is called unrank(index). It, on the other hand, translates the index into a permutation.

CodePudding user response：

There is an answer to a different question which offers code and an algorithm for ranking and unranking permutations in linear arithmetic operations. The catch is, the ranks aren't lexicographic. If that works for you, then so should this solution. I'm not marking this as a duplicate since the questions differ.

Indexing ranked permutations into other ranked permutations

The answer is based on this paper: Ranking & Unranking Permutations in Linear Time, by Myrvold & Ruskey, Information Processing Letters Volume 79, Issue 6, 30 September 2001, Pages 281–284.

http://webhome.cs.uvic.ca/~ruskey/Publications/RankPerm/MyrvoldRuskey.pdf