5. óra
Á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
