Programozás‎ > ‎

Kombinatorikus algoritmusok

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



Variációk


Kombinációk


Partíciók