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.

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

StackExchange Computer Science Q#155678, answer score: 9