NézetNyomtat

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

5. óra

(2008.10.14.)
Átnézzük a kombinációk előállításának algoritmusát, hogy teljes legyen az arzenál.

Kombinációk

Egy $n$ elemű halmaz $k$ elemű részhalmazait kell felsorolnunk. A részhalmazokat az elemek indexével adjuk meg, vagyis az $\{1,2,3,\ldots,n\}$ index-halmazból kell $k$ különböző számot kiválasztanunk, minden lehetséges módon.
A kiválasztott indexeket úgy képzeljük el, hogy $n$ rekeszünk van, az első $k$-ba beírunk 1-eseket, majd tologatni kezdjük az 1-eseket. Balról jobbra haladunk, és ha egy elem már nem tolható jobbra, akkor visszatesszük kiinduló helyzetébe. Az első olyan elemet, ami még mehet jobbra, eggyel jobbra léptetjük.
Például az 5-elemű halmaz 3-elemű részhalmazai:
Ugyanez indexekkel:
123, 124, 134, 234, 125, 135, 235, 145, 245, 345
Az a[1], a[2],...,a[k] értékek adják meg, hol vannak az 1-esek, és ez egyben az aktuális részhalmaz indexeinek listája is.
Az algoritmus két "strázsát" használ: a[k+1] = n + 1 és a[k+2] = 0.
a[j] := j, ha 1 <= j <= k és a[k+1] := n+1, a[k+2] := 0
Ciklus
    az a[1],a[2],...,a[k] kombináció bejárása
    j := 1
    Ciklus amíg a[j] + 1 = a[j+1]
        a[j] := j
        j := j + 1
    Ciklus vége
    Ha j > k akkor kilépés a főciklusból
    a[j]:=a[j] + 1
Ciklus vége

Feladat