5
$\begingroup$

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.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
6
$\begingroup$

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<k_1\\k_i-1&\text{otherwise} \end{array}\right.$$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks! The time complexity could even be lowered to O(nlogn) using prefix sums and a binary index tree. $\endgroup$
    – LogicalX
    Commented Nov 24, 2022 at 18:32
  • 1
    $\begingroup$ 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)) $\endgroup$
    – Stef
    Commented Nov 25, 2022 at 9:09
9
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.