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