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.