2386. The next permutation

Find the next permutation. Assume that permutation (n, n – 1, ..., 2, 1) is followed by the identity (1, 2, ..., n – 1, n).

Input. First line contains the number n (1 ≤ n ≤ 10⁵) of elements in the permutation. The second line contains a permutation of n integers.

Output. Print n numbers – the next permutation for the given one.

Sample input	Sample output
3 3 2 1	1 2 3

SOLUTION

combinatorics

Algorithm analysis

To generate the next permutation, we’ll use the next_permutation function. For the lexicographically largest permutation (n, n – 1, …, 2, 1) the next is the lexicographically smallest one (1, 2, ..., n – 1, n).

Let us describe an algorithm for finding the lexicographically next permutation. The permutation P = (p₁, p₂, …, p_n) is less than Q = (q₁, q₂, …, q_n) if there exists position i, for which p_i < q_i, and p_j = q_j for all j < i. For example

(3, 5, 4, 6, 7) < (3, 5, 6, 4, 7)

Let us show by an example how to find the next permutation for

P = (5, 6, 7, 4, 3)

Iterate through the current permutation from right to left until the next number is greater than the previous one. Stop when the rule is broken. Mark (underline) this position: (5, 6, 7, 4, 3). Again iterate the traversed path (from right to left) until we reach the first number that is greater than the marked one. The place of the second stop is marked with double underlining: (5, 6, 7, 4, 3). Swap the marked numbers: (5, 7, 6, 4, 3). Now sort all the numbers to the right of the double underlined integer in ascending order. Since they have so far been ordered in descending order, it is enough to reverse the indicated segment. We get Q = (5, 7, 3, 4, 6). This permutation is next after P.

Example

Find the permutation following P = (7, 5, 3, 6, 4, 2, 1).

Algorithm realization

Declare an array to generate permutations.

int m[MAX];

Read the input data.

scanf("%d",&n);

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

Generate the next permutation using next_permutation function. If the current permutation is the lexicographically largest one, then after calling the next_permutation function, the array m will take the form (1, 2, …, n – 1, n).

next_permutation(m,m+n));

Print the next permutation.

for(i = 0; i < n; i++)

printf("%d ",m[i]);

printf("\n");