NézetNyomtat

2. óra - Permutáció
Elmélet > Algoritmusok > Kombinatorikai algoritmusok
Címkék > Óra

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.
nn!
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