2. óra
(2008.09.23.)
Folytatjuk a kombinatorikus algoritmusok tanulmányozását.
Permutációk
Adott néhány szám (objektum), és ezeket minden lehetséges módon sorba kell rendeznünk.
A számok között lehetnek azonosak is.
Például az {1,2,3} számok permutációi: 123, 132, 213, 231, 312, 321; az {1,1,2,3} számok permutációi: 1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211.
Sorrend
A permutációkat lexikografikus sorrendben állítjuk elő. Ez azt jelenti, hogy a permutációkat "karakterláncoknak" képzeljük, és ezeket a karakterláncokat ábécé rend szerint rendezzük. Az "ábécében" a kisebb szám előbb van.
Az 1,2,3,...,n permutációból indulunk ki, és mindig a "legkisebb növelés" elve alapján keressük a következő permutációt. Ehhez az aktuális sorozat jobb szélétől (végétől) visszafelé keressük az első olyan elemet, amitől jobbra nála nagyobb elem van. Ha megtaláltuk, kicseréljük jobbról az első, nála nagyobb elemmel, majd a sorozat végének (ami most fordítottan rendezett) megfordítjuk a sorrendjét.
Következő permutáció
Algoritmus
Ciklus
az a[1],a[2],...,a[n] permutáció bejárása
j := n – 1
Ciklus amíg a[j] >= a[j+1]
j := j – 1
Ciklus vége
Ha j = 0 akkor kilépés a főciklusból
m := n
Ciklus amíg a[j] >= a[m]
m := m - 1
Ciklus vége
Csere( a[j], a[m] )
k := j + 1; m := n
Ciklus amíg k < m
Csere( a[k], a[m] )
k := k + 1; m := m - 1
Ciklus vége
Ciklus vége
Lépésszám
Az összes permutáció "legyártása" csak "kis" $n$ esetén lehetséges.
| n | n! |
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 6 | 720 |
| 7 | 5040 |
| 8 | 40320 |
| 9 | 362880 |
| 10 | 3628800 |
| 11 | 39916800 |
| 12 | 479001600 |
| 13 | 6227020800 |
| 14 | 87178291200 |
| 15 | 1307674368000 |
| 16 | 20922789888000 |
Feladat
