Feladat: I.28 Korcsoport: - Nehézségi fok: -
Füzet: 2002/szeptember, 357 - 358. oldal  PDF  |  MathML 
Témakör(ök): Feladat

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.

Minden permutáció előállítható ciklikus módon. Az (i1,...,ik) ciklus azt jelenti, hogy az i1-edik elemet az i2-edik, az i2-edik elemet az i3-adik, ..., az ik-1-edik elemet az ik-adik, az ik-adik elemet pedig az i1-edik pozícióba kell mozgatni ahhoz, hogy mindegyikük a saját helyére kerüljön. Minden permutáció leírható egymástól független ciklusokkal.
Például az (1,2,3,4,5,6,7) sorozat egy permutációja a (4,3,2,7,5,1,6) sorozat ciklikus leírása az (1,4,7,6), (2,3), (5) három ciklusból álló sorozat, azaz az eredeti helyreállítható úgy, hogy az első elemet a negyedik helyre tesszük, a negyedik helyen levőt a hetedikre, ...
Készítsünk programot (I28.pas,...), amely beolvassa N értékét és az első N szám egy permutációját, majd megadja az ezt növekvő sorrendbe rendező ciklusokat!