Next Permutation

A permutation of a set is simply a sequence that contains each member of that set exactly once. For example, ⟨4, 2, 5, 1, 3⟩ is a permutation of the set {1, 2, 3, 4, 5}, as is ⟨4, 2, 1, 3, 5⟩.

Let n be a positive integer, and let S = ⟨x₁, x₂, …, x_n⟩ and T = ⟨y₁, y₂, …, y_n⟩ be permutations of the set {1, 2, …, n}. Then we define S < T (S is “less than” T) to mean that there exists k, 1 ≤ k ≤ n, such that x_k < y_k and x_i = y_i for all i satisfying 1 ≤ i < k. In other words, S < T means that, in the first position at which S and T disagree, S has the element of lesser value.

For example,

⟨4, 2, 1, 3, 5⟩ < ⟨4, 2, 5, 1, 3⟩

because in the first position where the two sequences disagree (namely, the third position), the permutation on the left has a smaller value (1) than does the permutation on the right (5).

It should be clear that, by this definition, we can list all the permutations of {1, 2, …, n} in order, from least (⟨1, 2, …, n⟩) to greatest (⟨n, n – 1, n – 2, …, 1⟩).

As an example, here are the permutations of {1, 2, 3, 4} in order from least to greatest:

⟨1, 2, 3, 4⟩, ⟨1, 2, 4, 3⟩, ⟨1, 3, 2, 4⟩, ⟨1, 3, 4, 2⟩, ⟨1, 4, 2, 3⟩, ⟨1, 4, 3, 2⟩, ⟨2, 1, 3, 4⟩, ⟨2, 1, 4, 3⟩, ⟨2, 3, 1, 4⟩, ⟨2, 3, 4, 1⟩, ⟨2, 4, 1, 3⟩, ⟨2, 4, 3, 1⟩, ⟨3, 1, 2, 4⟩, ⟨3, 1, 4, 2⟩, ⟨3, 2, 1, 4⟩, ⟨3, 2, 4, 1⟩, ⟨3, 4, 1, 2⟩, ⟨3, 4, 2, 1⟩, ⟨4, 1, 2, 3⟩, ⟨4, 1, 3, 2⟩, ⟨4, 2, 1, 3⟩, ⟨4, 2, 3, 1⟩, ⟨4, 3, 1, 2⟩, ⟨4, 3, 2, 1⟩

Develop a program that, given a positive integer n and a permutation S of the set {1, 2, …, n}, computes the smallest permutation T such that S < T.

Hint: Let S = ⟨x₁, x₂, …, x_n⟩ and suppose that x_j < x_j+1 > x_j+2 > x_j+3 > … > x_n. (In other words, suppose that j is the last position in S at which an element is smaller than the next element.) Then the smallest permutation T greater than S is of the form ⟨x₁, x₂, …, x_j–1, x_k, …⟩, where x_k is the smallest element among {x_j+1, x_j+2, …, x_n} that is larger than x_j. End of hint.

Input Specification

The first line contains the number m > 0 of permutations that will be provided in the remaining input. The next 2m lines contain those permutations, each one described on two lines, the first of which contains a positive integer n and the second of which contains the permutation itself (i.e., a sequence containing each member of {1, 2, …, n} exactly once), with spaces separating its elements. You may assume that none of the permutations given is the largest one possible. (That is, none of them will be of the form ⟨n, n – 1, …, 1⟩.) You may also assume that n ≤ 30.

Output Specification

For each permutation S given as input, generate three lines of output: the first should display S, the second should display the smallest permutation that is larger than S, and the third should be blank.

Sample Input

3
4
2 4 1 3
6
5 2 6 4 3 1
14
4 14 12 10 3 13 6 7 11 9 8 5 2 1

download as text file

Output for Sample Input

2 4 1 3
2 4 3 1
5 2 6 4 3 1
5 3 1 2 4 6
4 14 12 10 3 13 6 7 11 9 8 5 2 1
4 14 12 10 3 13 6 8 1 2 5 7 9 11