|
|||
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 = ⟨x1, x2, …, xn⟩ és T = ⟨y1, y2, …, yn⟩ 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 xk < yk és xi = yi 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 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:
Í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 = ⟨x1, x2, …, xn⟩, és tegyük fel, hogy xj < xj+1 > xj+2 > xj+3 > … > xn. (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, ⟨x1, x2, …, xj–1, xk, …⟩ alakú, ahol xk a legkisebb olyan eleme az {xj+1, xj+2, …, xn} halmaznak, amely nagyobb, mint xj. A bemenet specifikációjaAz 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ójaA 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
A példa bemenethez tartozó kimenet
|
|||
Debreceni Egyetem, Informatikai Kar, v. 2024.09.30. |