Kombinatorikus algoritmusok

Tartalom

1 Permutációk
2 Variációk
3 Kombinációk
4 Partíciók

Ha egy matematikai probléma megoldására nincs ötletünk, reménykedhetünk számítógépünk sebességében. Ilyenkor (jobb híján) a „nyers erő” módszerével oldhatjuk meg a feladatot, ami azt jelenti, hogy valamilyen rendszer szerint végignézzük az összes lehetséges esetet. Első ránézésre ez meglehetősen primitív problémamegoldási stratégiának tűnhet, de a ma elérhető számítási kapacitások mellett komoly eredmények nyerhetők ezzel a technikával. (Négyszín-tétel, Mersenne prímek, a SET játék elemzése…)

Gyakran nem egy nyitott kérdés megoldása a cél, csupán kellő számú példa előállítása, melyek alapján sejtést próbálunk megfogalmazni. A próbálgatás (tudományos kísérlet), mindig is része volt a matematikai felfedezésnek, a számítógépek csupán egy minden eddiginél hatékonyabb eszközt adnak a matematikus kezébe a kísérletek végrehajtására.

Kifinomultabb algoritmusokban szükség lehet egy halmaz valamelyik elemének véletlenszerű kiválasztására. (Feltételezzük, hogy rendelkezésünkre áll egy megfelelő álvéletlen generátor.) Ilyenkor a hatékonyság mellett fontos az is, hogy minden lehetséges kiválasztás egyenlő valószínűséggel történhessen meg.

A következő pontokban bemutatunk néhány ismert algoritmust az alapvető kombinatorikai objektumok felsorolására.

Permutációk

Nyers erő

Ismert, hogy n különböző elemnek n! féle sorrendje van. A nagyságrendről képet alkothatunk, ha megjegyezzük, hogy egy 32-bites számítógépeken a 13!= 6227020800 már nem ábrázolható egy gépi szóban. (Kettes számrendszerben felírva több, mint 32 jegyű.) Még a leggyorsabb számítógépet használva sem várhatjuk, hogy n > 20 esetén n! darab eset végignézése egy nap alatt befejeződik.

Egy n elemű permutáció egy olyan n jegyű, n alapú számrendszerben felírt szám, melynek jegyei különböznek. Tehát nem kell mást tennünk, mint egyesével számolunk, és az aktuális szám n alapú felírásáról eldöntjük, hogy különböznek-e a jegyei.

A valóság az, hogy ez nem túl ügyes „megoldás”. Az n! darab permutáció legyártásához nⁿ darab számot vizsgáltunk.

Iteratív módszer - lexikografikus sorrend (Donald Knuth)

Kiindulunk a 0, 1, 2, ..., N - 1 permutációból, és mindig a legkisebb csökkenés elve alapján keressük a következő permutációt. (Ehhez most is képzelhetjük úgy, hogy egy N-es számrendszerben felírt számot növelgetünk.)

Elvégezzük teendőnket az aktuális permutációval. (Például kiírjuk.)
Ha a sorozat csökkenően rendezett, akkor vége a permutációk felsorolásának.
Különben

Jobbról megkeressük az első elemet, ami kisebb a nála jobbra állónál. (Ezen a pozíción fogunk növelni.)
Indexe: j
Jobbról megkeressük az első elemet, ami nagyobb, mint az előbb kiválasztott a[ j ] elem
Indexe: m
Felcseréljük az a[ j ] és a[ m ] elemeket.
Most a (j+1)-től a sorozat végéig tartó szakasz fordítottan rendezett
Megfordítjuk a (j+1)-től a sorozat végéig tartó szakaszt.

Ezután az első ponttól folytatódik az eljárás

Rekurzív módszer (Robert Sedgewick)

Forrás.

Kiindulunk a 0, 1, 2, ..., N - 1 permutációból, és minden lehetséges elemet becserélünk az első helyre, majd a mögötte lévő szakaszt rekurzív "permutáljuk".

A rekurzív eljárás egy i indexű elemtől kezdődően, a tömb végéig tartó szakaszt rendezgeti. Az elsö indexre kell elindítani az eljárást.

RekurzívPermutáció(i)
Ha i nagyobb a maximális indexnél akkor az aktuális permutáció feldolgozása
különben
      Ciklus k := i-től az utolsó indexig
          csere(i, k)
          RekurzívPermutáció(i + 1)
          csere(i, k)
      Ciklus vége
Eljárás vége

Véletlen permutáció avagy keverés

Permutáció rangja

Sokszor hasznos, ha anélkül tudjuk megadni az i. permutációt, hogy legenerálnánk az összes előtte lévőt. Fordítva: érdekelhet minket egy adott permutáció rangja, vagyis az, hogy lexikografikus sorrendben hányadik ez a permutáció.