Next permutation
Given a table with n integers, compute the permutation which comes lexicographically next, or answer that the given order is maximal.
The given table does not have to be a permutation on \(\{0,1,\ldots,n-1\}\), it can contain elements with multiplicity.
Key observation
Given a table \(t=(t_0,t_1,\ldots,t_{n-1})\) we want to transform it into the lexicographically next one. For this purpose we want to preserve a longest prefix of t, and have a lexicographically smallest suffix.
A linear time algorithm
The algorithm consists in 3 steps. First we need to find the largest index p — called pivot — such that t[p] < t[p+1]. The idea is that the suffix of t starting at p+1 is a non-increasing sequence and therefore lexicographically maximal. It such a pivot does not exist, we know that t is already lexicographically maximal.
Now it is clear that t[p] has to be increased, but in a minimal manner. Hence we search for an index s such that t[s] is minimal and t[s] > t[p]. Since p+1 is a valid candidate, such an index always exist.
Once we swapped t[p] with t[s] we obtain a table that is lexicographically larger than the initial table t. Finally we can sort the suffix of t starting at p+1, in order to obtain a smallest permutation that is lexicographically larger than t. Note that in order to sort this suffix it suffices to reverse it.
Example
initial table | 0 | 2 | 1 | 6 | 5 | 2 | 1
choose pivot | 0 | 2 | [1] | 6 | 5 | 2 | 1
swap | 0 | 2 | [2] | 6 | 5 | [1] | 1
reverse | 0 | 2 | 2 | [1 | 1 | 5 | 6]
final table | 0 | 2 | 2 | 1 | 1 | 5 | 6