# Compute Permutation Number

Given a permutation on the array of integers 1 through n, I want to find the index of the permutation in a list of all possible permutations of those integers, sorted in lexicographic order.

For example, given the permutation {1, 3, 2} with n=3, I want the program to return 1, because the array has 6 permutations ({{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}), and when all the permutations are sorted in lexicographic order, the given permutation is at index 1.

A possible solution is to go through every permutation, but this takes O(n!) time. Is there a way to do this in polynomial time?

This problem seems somewhat related to this one, but isn't the same.

If it helps, I am looking to write the code for this problem in C++.

Any potential clarifications are welcome.

A first observation is that for all $$k\in \{1, …, n\}$$, there are $$(n-1)!$$ permutations of size $$n$$ beginning with $$k$$.

For a permutation $$\sigma = (k_1, …, k_n)$$, that means that the rank of $$\sigma$$ is at least $$(k_1-1)\times (n-1)!$$.

What you can do to find the exact rank is updating $$(k_2, …, k_n)$$ by replacing each $$k_i$$ with $$k'_i$$ such that: $$k'_i = \left\{\begin{array}{ll}k_i&\text{if }k_i

The sequence $$\sigma'=(k'_2, …, k'_n)$$ is then a permutation of $$\{1, …, n-1\}$$. If $$R_n(\sigma)$$ represents the rank of $$\sigma$$ among permutations of size $$n$$, then:

$$R_n(\sigma) = (k_1-1)\times (n-1)! + R_{n-1}(\sigma')$$ This gives an algorithm in $$\mathcal{O}(n^2)$$ (assuming the computation of factorials is done in $$\mathcal{O}(1)$$, which may not be the case in the general case).

• Thanks! The time complexity could even be lowered to O(nlogn) using prefix sums and a binary index tree. Commented Nov 24, 2022 at 18:32
• I think the python implementation for permutation_index uses the same logic as your answer, but the sum of factorials has been factored differently, so that the recursive formula is a bit simpler. (Their code is also O(n²) although it may look O(n) at a glance: the del operation inside the loop corresponds to your "updating (k2, ..., kn) by replacing..." and is O(n))
– Stef
Commented Nov 25, 2022 at 9:09

This task is known as ranking permutations. It can be solved with the factorial number system (https://en.wikipedia.org/wiki/Factorial_number_system). See also https://stackoverflow.com/q/1506078/781723, https://stackoverflow.com/q/39839119/781723 for further explanations.

More generally, see ranking and unranking (https://oeis.org/wiki/Ranking_and_unranking_functions).