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