Guessing the answer & Solution

Observe Sample Input and Output 2.

• Input : \(\, 9, 8, 6, 5, 10, 3, 1, 2, 4, 7\)
• Output : \(\, 9, 8, 6, 5, 10, 2, 7, 4, 3, 1\)

We observe the following properties:

• The last \(5\) terms have changed, while the first \(5\) terms remains the same.
• The last \(4\) terms in the input monotonically increases, while the last \(4\) terms in the output monotonically decreases.

By the second property (the last \(4\) terms in the input monotonically increases), we cannot construct a permutation lexicographically smaller than the given term only by rearranging the last \(4\) terms. Therefore, we need to sort at least \(5\) last terms. The first property (the first \(5\) terms remains unchanged) can be considered as “we try to keep as many first terms as possible.” We prove this guess in the later section.

Let us generalize it. Since \(P \neq (1, \dots, N)\), we can take \(n\) such that \(P_n \gt P_{n + 1} \lt P_{n + 2} \lt \dots \lt P_N\). Since we cannot construct a permutation lexicographically smaller than \(P\) only by rearranging \(P_{n + 1}, \dots, P_N\), as we are trying to preserve the first terms as much as possible, the answer should be able to be obtained only by rearranging \(P_n, \dots, P_N\). Moreover, the \(n\)-th term should be different (otherwise, it is merely equivalent to rearranging \(P_{n + 1}, \dots, P_N\)).

Since we are trying to keep the first \((n-1)\) terms while change the \(n\)-th term, the resulting permutation is lexicographically smaller than \(P\) if and only if the \(n\)-th term is strictly less than \(P_n\). The answer is the largest permutation lexicographically smaller than \(P\), so we need to let the \(n\)-th term the largest of \(P_n, \dots, P_N\) that is less than \(P_n\). Under this constraint, no matter how we rearrange the \((n+1)\)-th and later terms, the resulting permutation is lexicographically smaller than \(P\). Therefore, the answer can be obtained by making the \((n+1)\)-th and later terms lexicographically largest, that is, by sorting the remaining elements in descending order.

The algorithm so far can be implemented in a total of \(O(N)\) time. The following are sample codes.

Sample code (C++)
Sample code (Python)

Proof of the guess

Now we must prove the guess above, or we cannot say we have solved this problem.
For sequences \(A\) and \(B\), let us denote \(A \lt B\) if \(A\) is lexicographically smaller than \(B\).

If two permutations \(X\) and \(Y\) satisfy \(X \lt P\) and \(Y \lt P\), then there exist integers \(n\) and \(m\) such that:

• \((X_1, \dots, X_{n - 1}) = (P_1, \dots, P_{n - 1}), X_n \lt P_n\);
• \((Y_1, \dots, Y_{m - 1}) = (P_1, \dots, P_{m - 1}), Y_m \lt P_m\).

Then we can see that, if \(n \lt m\), then \(X \lt Y\), by the following two facts:

• \((X_1, \dots, X_{n - 1}) = (P_1, \dots, P_{n - 1}) = (Y_1, \dots, Y_{n - 1})\)
• \(X_n \lt P_n = Y_n\)

Therefore, we have proven that the lexicographically largest permutation smaller than \(P\) is the one which the different value than \(P\) occurs as late as possible when inspected from the beginning.

Hence, our guess that “we have to try to keep as many first terms as possible” turns out to be true.

Another solution: using the standard library

C++ has a function called std::prev_permutation. By letting std::prev_permutation(std::begin(P), std::end(P)), the lexicographically largest permutation of \(P\) smaller than \(P\) is stored in \(P\).

We can implement it very easily using this function.

Sample code (C++)