Feladat: Pontversenyen kívüli P.289 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Horváth Nándor ,  Kriza György ,  Vértesi Nándor 
Füzet: 1978/szeptember, 19 - 20. oldal  PDF  |  MathML 
Témakör(ök): Algoritmikus eljárások, Pontversenyen kívüli probléma
Hivatkozás(ok):Feladatok: 1977/október: Pontversenyen kívüli P.289

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Először vizsgáljuk meg két szám esetét. Az összes permutációt cserével állíthatjuk elő: leírjuk a két számot eredeti sorrendben, majd egyszerűen felcseréljük őket: 1, 2; 2, 1. Három szám esetén már bonyolultabb a helyzet. A számok eredeti sorrendje: 1, 2, 3. Elsőként cseréljük meg az első kettőt, így előállítottunk egy új sorrendet: 2, 1, 3. Mivel az utolsó szám helyére nemcsak a hármas, hanem más szám is kerülhet, alkalmazzuk a következő módszert. Cseréljük vissza a két első számot (így a kiindulási sorrendet kapjuk vissza), majd léptessük mindhárom számot ciklikusan balra, így: 2, 3, 1. Ezzel egy új permutációt kaptunk, melyben egy másik szám (az 1-es) áll az utolsó helyen. Ha most ebben a permutációban az első két számot felcseréljük, akkor ezzel az összes olyan permutációt megkapjuk, amelyben az 1-es áll hátul. Cseréljük vissza a két első számot és ismét léptessük balra. Így a 2-es kerül hátra, és újabb kétféle permutációt kapunk. Ha harmadszor is balra léptetünk, az eredeti kiindulási sorrendet (1, 2, 3) kapjuk vissza.
Az első 100 szám esetében is hasonlóan járunk el. Először az első két számot cseréljük fel (vagy ami ugyanaz, léptetjük ciklikusan balra), majd az eredeti sorrend helyreállítása után az első hármat stb. Az első N számot összesen N-szer léptetjük balra, az N-edik lépés után az eredeti (a számok léptetése előtti) sorrend áll vissza. Ezután az első N+1 számot léptetjük eggyel balra stb.

 
 

A program, melynek blokkdiagramját az ábra mutatja, a permutációkat az X tömbben állítja elő. Az Y tömbben tároljuk, hogy hányszor kell még léptetnünk. Kezdetben az X(N) és Y(N) értéke N minden 1N100-ra.
A programot a TPA kis számológép FOKAL programnyelvén írtam meg. Az összes permutáció kinyomtaásához egy ember élete is kevés volna.
 
 Horváth Nándor (Miskolc, Földes F. Gimn., IV. o. t.)
 

Megjegyzés. A fenti eljárás FORTRAN nyelvű programja a következő:
 

INTEGER X(100), Y(100)  1FORMAT (10 X, 2514)DO 2 N = 1,100X(N) = N  2Y(N) = N  3WRITE(3,1)XN = 1  4N = N + 1K = X(1)DO 5 I = 2,N  5X(I - 1) = X(I)X(N) = KIF(Y(N). EQ.1) GOTO 6Y(N) = Y(N) - 1GOTO 3  6Y(N) = NIF(N.LT.100) GOTO 4STOPEND