Permutácie

Prvým spôsob ako generovať všetky možnosti sú permutácie. Zoberme si napríklad nasledujúcu úlohu pamiatky. V tejto úlohe máme $n$ pamiatok a na svojej výhliadkovej túre si ich chceme všetky postupne pozrieť. Každá pamiatka nám však pridá alebo uberie radosť z výletu. Samozrejme nechceme, aby naša radosť bola pod $0$. Otázka je, koľko je takých postupností návštevy pamiatok, že naša radosť neklesne pod $0$.

Vieme, že existuje najviac $n!$ rôznych poradí návštev pamiatok, keďže každá permutácia pamiatok určuje jednu postupnosť, ktorou sa môžeme vybrať. Takisto vieme, že v najväčšom možnom vstupe je $n=9$, takže rôznych permutácií je $9!=362\,880$. A to vôbec nie je tak veľa.

No a úplne najlepšia správa je, že ak vám dám konkrétnu permutáciu pamiatok, viete veľmi jednoducho zistiť, či táto permutácia poruší podmienku zo zadania a teda radosť z jej prejdenia klesne pod $0$. Na to stačí simulovať prechádzku po pamiatkach a stále si pamätať, akú máme momentálne radosť. Ak niekedy klesne pod $0$, daná postupnosť je zlá, ak sa to nikdy nestane, môžeme si pripočítať $1$ k výsledku.

Ten najdôležitejší krok však zostáva. Ako si vygenerovať postupne všetky permutácie čísel od $1$ po $n$. Poprípade to ani nemusia byť prvky od $1$ po $n$, môžu to byť aj čísla oveľa väčšie alebo opakujúce sa.

Prvou možnosťou je urobiť si vlastnú rekurzívnu funkciu. Ako parametre dostane táto funkcia dve polia: prvé obsahuje prvky, ktoré ešte nepoužila a treba ich zaradiť do vytváranej permutácie, druhá obsahuje prvky, ktoré vytvárajú aktuálnu permutáciu. To, čo treba spraviť ako ďalší krok, je vybrať prvok, ktorý bude ležať na ďalšom mieste v našej permutácii. A vhodní kandidáti sú všetky ešte nezaradené prvky. No a keďže chceme vytvoriť permutácie všetky, postupne skúšame dosadiť všetky nezaradené prvky na ďalšie voľné miesto. Keď si zvolíme prvok $x$, vyberieme ho z nezaradených prvkov, pridáme ho do permutácie a znova sa rekurzívne vnoríme.

Keď spotrebujeme všetky prvky, ostane nám výsledná permutácia. A tento prístup ich postupne vygeneruje všetky. Tu je k tomu názorný program:

//rekurzivna funkcia tvoriaca permutacie
void permutacie(vector<int> nezaradene, vector<int> permutacia) {
    if(nezaradene.size()==0) {
        //už som zaradil všetky prvky, spravím niečo s výslednou permutáciou
        return ;
    }
    //postupne dám na ďalšie miesto každý prvok
    for(int i=0; i<nezaradene.size(); i++) {
        //v nove_nezaradene nie je prvok nezaradene[i]
        vector<int> nove_nezaradene;
        for(int j=0; j<i; j++) nove_nezaradene.push_back(nezaradene[j]);
        for(int j=i+1; j<nezaradene.size(); j++) nove_nezaradene.push_back(nezaradene[j]);
        //v nova_permutacia pribudne na koniec prvok nezaradene[i]
        vector<int> nova_permutacia = permutacia;
        nova_permutacia.push_back(nezaradene[i]);
        //rekurzivne sa zavolám
        permutacie(nove_nezaradene, nova_permutacia);
    }
}

Nevýhodou na tomto riešení je, že si posúva dve polia ako parametre funkcie. To ho dosť spomaľuje. Samozrejme, dá sa toho zbaviť, ale napriek tomu potrebujeme napísať sami zbytočne veľa kódu, v ktorom je veľká šanca, že sa pomýlime. Niekto však ten kód už napísal za nás, tak prečo ho nepoužiť.

V STL existuje funkcia next_permutation(), ktorá ako napovedá názov vytvorí z poľa, ktoré jej dáme ako parameter ďalšiu jeho permutáciu. A toto má množstvo výhod. Nemusíme skoro nič programovať, všetko dostaneme zadarmo. Túto funkcia môžeme používať opakovane a prejsť tak postupne cez všetky možné permutácie. A taktiež vždy nájde permutáciu, ktorá je lexikograficky väčšia. To znamená, že ak pole obsahuje niekoľko rovnakých prvkov, táto funkcia vie preskočiť všetky také, ktoré sa líšia len výmenou niektorých dvoch rovnakých. Ak teda máme $n$ prvkov a $p$ z nich sú rovnaké a ostatné sú rôzne, tak namiesto $n!$ možností vygeneruje len $\frac{n!}{p!}$.

Jediné, na čo si treba dať pozor je, že na začiatku chcete dať do tejto funkcie prvky usporiadané od najmenšieho po najväčší. Toto je totiž lexikograficky najmenšia permutácia a ako som spomínal next_permutation() vytvára vždy väčšiu. Tu si môžete pozriež najčastejšie použitie tejto funkcie:

//potrebný include
#include <algorithm>

//prvky, ktoré chcem permutovať
vector<int> permutacia;
//musím si prvky zoradiť
sort(permutacia.begin(),permutacia.end());
do{
    //v poli permutacia je ďalšia permutácia, tak ju spracujeme
}while(next_permutation(permutacia.begin(),permutacia.end()))

Bude veľmi dobré, ak sa tento kúsok kódu naučíte, zíde sa vám, keď budete potrebovať generovať všetky permutácie.