A következő permutáció

Egy halmaz permutációja alatt egy olyan sorozatot értünk, amely a halmaz minden elemét pontosan egyszer tartalmazza. A ⟨4, 2, 5, 1, 3⟩ például az {1, 2, 3, 4, 5} halmaznak egy permutációja, mint ahogy a ⟨4, 2, 1, 3, 5⟩ is.

Legyen n egy pozitív egész szám, legyen továbbá S = ⟨x₁, x₂, …, x_n⟩ és T = ⟨y₁, y₂, …, y_n⟩ az {1, 2, …, n} halmaz permutációi. Ekkor azt mondjuk, hogy S < T (S „kisebb, mint” T), ha létezik olyan k (1 ≤ k ≤ n), amelyre x_k < y_k és x_i = y_i minden olyan i esetén, amelyre 1 ≤ i < k. Más szóval S < T azt jelenti, hogy az első olyan pozícióban, ahol S és T eltérnek egymástól, S-ben található a kisebb értékű elem.

Például

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

teljesül, mert az első olyan pozícióban, ahol a két sorozat eltér egymástól (ez a harmadik pozíció), a bal oldali permutációban kisebb érték (1) szerepel, mint a jobb oldaliban (5).

Nyilvánvaló, hogy a fenti definíció alapján kilistázhatjuk az {1, 2, …, n} halmaz összes permutációját rendezetten, a legkisebbtől (⟨1, 2, …, n⟩) a legnagyobbig (⟨n, n – 1, n – 2, …, 1⟩).

Példaként álljon itt az {1, 2, 3, 4} halmaz összes permutációja rendezve, a legkisebbtől a legnagyobbig:

⟨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⟩

Írj programot, amely egy adott n egész szám és az {1, 2, …, n} halmaz egy adott S permutációja estén kiszámítja a legkisebb olyan T permutációt, amelyre S < T!

Segítség: Legyen S = ⟨x₁, x₂, …, x_n⟩, és tegyük fel, hogy x_j < x_j+1 > x_j+2 > x_j+3 > … > x_n. (Más szóval tegyük fel, hogy j az utolsó olyan pozíció S-ben, ahol az elem kisebb a következő elemnél.) Ekkor a legkisebb olyan T permutáció, amely nagyobb, mint S, ⟨x₁, x₂, …, x_j–1, x_k, …⟩ alakú, ahol x_k a legkisebb olyan eleme az {x_j+1, x_j+2, …, x_n} halmaznak, amely nagyobb, mint x_j.

A bemenet specifikációja

Az első sor egy m > 0 számot, a bemenet további részében megadott permutációk számát tartalmazza. A következő 2m sorban szerepelnek a permutációk, mindegyik két sorban: az első egy n pozitív egész számot tartalmaz, a második pedig magát a permutációt (azaz egy olyan sorozatot, amely az {1, 2, …, n} halmaz minden elemét pontosan egyszer tartalmazza). A permutációk elemeit egy-egy szóköz választja el egymástól. Feltételezheted, hogy egyik megadott permutáció sem lesz a lehetséges legnagyobb. (Ez azt jelenti, hogy egyik sem lesz ⟨n, n – 1, …, 1⟩ alakú.) Feltételezheted továbbá, hogy n ≤ 30.

A kimenet specifikációja

A bemeneten megadott minden S permutációra három sort kell a kimenetre írni: az elsőnek S-et kell tartalmaznia, a másodiknak a legkisebb olyan permutációt, amely nagyobb, mint S, a harmadiknak pedig üresnek kell lennie.

Példa bemenet

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

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

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