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.

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

Langford permutációk