KOMBINATORNI PROBLEMI- PRIMERI

Uputstvo — kako razmišljati

Varijaciju možemo posmatrati kao broj zapisan u “osnovi” n, samo što umesto cifara 0, 1, 2, ... koristimo vrednosti od 1 do n.

Kao i kod običnog broja, narednu varijaciju dobijamo tako što:

• krenemo od desnog kraja,
• pokušamo da uvećamo poslednji element,
• ako je on već jednak n, vraćamo ga na 1 i “prenosimo” dalje ulevo.

To je potpuno isto kao sabiranje jedinice pri prelasku preko najveće cifre.

Ključna ideja

Posmatramo varijaciju s desna na levo. Ako je neki element jednak n, on ne može dalje da raste, pa ga menjamo u 1.

Kada pronađemo prvi element koji nije n, njega uvećamo za 1 i time dobijamo narednu varijaciju.

Svi elementi desno od tog mesta već su postavljeni na 1, jer je to najmanja moguća vrednost.

Primer rada

1 1 2 3 4
        ^
        poslednji element je 4 = n, pa preliva na 1

1 1 2 3 1
      ^
      sada i ovaj element postaje 4 = n, pa preliva na 1

1 1 2 4 1
    

Tako dobijamo narednu varijaciju u leksikografskom poretku.

Kada nema naredne varijacije?

Ako su svi elementi jednaki n, tada je varijacija već poslednja. Na primer:

4 4 4 4 4
    

U tom slučaju ispisujemo -.

Složenost

U najgorem slučaju prolazimo kroz celu varijaciju jednom:

O(k)
    

Memorija je:

O(k)
    

#include <iostream>
#include <vector>
using namespace std;

// ------------------------------------------------------------
// Funkcija određuje narednu varijaciju u leksikografskom poretku.
// Varijacija je zapisana brojevima od 1 do n.
// 
// Ideja:
// - krećemo od desnog kraja
// - ako je element jednak n, vraćamo ga na 1 i prelazimo ulevo
// - kada nađemo element koji nije n, uvećamo ga za 1
// - ako su svi elementi bili n, nema naredne varijacije
// ------------------------------------------------------------
bool sledecaVarijacija(vector<int>& varijacija, int n) {
    int k = (int)varijacija.size();
    int poz = k - 1;

    // Dok god je trenutni element maksimalan, postavljamo ga na 1
    // i pomeramo se ulevo.
    while (poz >= 0 && varijacija[poz] == n) {
        varijacija[poz] = 1;
        poz--;
    }

    // Ako smo prošli kroz celu varijaciju, ona je već poslednja.
    if (poz < 0) return false;

    // Prvi element koji nije bio n povećavamo za 1.
    varijacija[poz]++;

    return true;
}

int main() {
    int k, n;
    cin >> k >> n;

    vector<int> varijacija(k);

    // Učitavamo varijaciju dužine k.
    for (int i = 0; i < k; i++) {
        cin >> varijacija[i];
    }

    if (sledecaVarijacija(varijacija, n)) {
        // Ispisujemo novu varijaciju.
        for (int x : varijacija) {
            cout << x << ' ';
        }
        cout << '\n';
    } else {
        // Ako naredna varijacija ne postoji.
        cout << "-\n";
    }

    return 0;
}
    

Završno objašnjenje

Ovaj zadatak je varijanta “brojanja unapred” u sistemu gde su dozvoljene vrednosti od 1 do n.

Najbitnije je da desni kraj posmatramo kao najmanje značajne cifre:

• ako može da se poveća, povećavamo ga;
• ako ne može, vraćamo ga na 1 i prelazimo na sledeću poziciju ulevo;
• kada nađemo poziciju koja može da se poveća, tu stajemo.

Zato je rešenje jednostavno, brzo i radi u linearnom vremenu.

Uputstvo — kako razmišljati

Potrebno je ispisati sve moguće varijacije dužine k sastavljene od brojeva 1, 2, ..., n.

Pošto je dozvoljeno ponavljanje, na svakoj poziciji možemo postaviti bilo koji broj od 1 do n.

Ključna ideja

Varijaciju gradimo postepeno, jednu poziciju po jednu.

Za svaku novu poziciju imamo:

• n mogućih izbora,
• svaki izbor vodi ka novim varijacijama.

Zato je prirodno koristiti rekurziju.

Kako radi rekurzija?

Pretpostavimo da je:

n = 2
k = 3

Prvo biramo prvi element:

1
2

Ako smo izabrali:

1

onda za sledeću poziciju ponovo možemo birati:

1 1
1 2

Zatim nastavljamo na isti način sve dok ne formiramo varijaciju dužine k.

Kada ispisujemo rezultat?

Kada trenutna varijacija dostigne dužinu:

k

tada smo formirali jednu kompletnu varijaciju i možemo da je ispišemo.

Zašto je poredak leksikografski?

Brojeve dodajemo redom:

1, 2, ..., n

na svakoj poziciji.

Zbog toga se varijacije generišu upravo onim redosledom kojim bi se pojavile u leksikografskom poretku.

Broj varijacija

Na svakoj od k pozicija imamo po n izbora.

Ukupan broj varijacija je:

n^k

Zato algoritam mora da obiđe svih n^k mogućnosti.

#include <iostream>
#include <vector>
using namespace std;

// ------------------------------------------------------------
// Rekurzivno generišemo sve varijacije sa ponavljanjem.
//
// varijacija
// trenutno formirana varijacija.
//
// Kada njena dužina postane k,
// ispisujemo je.
// ------------------------------------------------------------
void generisiVarijacije(
    int n,
    int k,
    vector<int>& varijacija
) {

    // --------------------------------------------------------
    // Formirana je kompletna varijacija.
    // --------------------------------------------------------
    if ((int)varijacija.size() == k) {

        for (int broj : varijacija) {
            cout << broj << ' ';
        }

        cout << '\n';
        return;
    }

    // --------------------------------------------------------
    // Na sledeću poziciju možemo staviti
    // bilo koji broj od 1 do n.
    // --------------------------------------------------------
    for (int i = 1; i <= n; i++) {

        // dodajemo broj
        varijacija.push_back(i);

        // popunjavamo ostatak varijacije
        generisiVarijacije(n, k, varijacija);

        // vraćamo stanje pre sledećeg pokušaja
        varijacija.pop_back();
    }
}

int main() {

    int n, k;
    cin >> n >> k;

    vector<int> varijacija;

    generisiVarijacije(n, k, varijacija);

    return 0;
}

Završno objašnjenje

Ovo je jedan od najjednostavnijih primera rekurzivnog generisanja.

Umesto da unapred znamo celu varijaciju, gradimo je korak po korak:

• izaberemo broj za narednu poziciju,
• rekurzivno popunjavamo ostatak,
• vratimo se nazad i probamo sledeći izbor.

Backtracking

Instrukcija:

varijacija.pop_back();

vraća nas u prethodno stanje.

Ovakav način pretrage naziva se backtracking.

Nakon što obradimo sve mogućnosti koje počinju jednim izborom, vraćamo se korak unazad i pokušavamo sledeći.

Ključna lekcija

Kada treba generisati:

• sve varijacije,
• sve kombinacije,
• sve podskupove,
• sve reči određene dužine,

veoma često je najprirodnije rešenje upravo rekurzija i backtracking.

Uputstvo — kako razmišljati

Potrebno je generisati sve moguće reči dužine k.

Na svakoj poziciji možemo izabrati bilo koje slovo iz stringa s.

Pošto je dozvoljeno ponavljanje slova, svaka pozicija ima isti skup mogućih izbora.

Ključna ideja

Reč gradimo slovo po slovo.

Za svaku novu poziciju:

• biramo jedno slovo iz stringa,
• dodajemo ga na kraj trenutne reči,
• rekurzivno popunjavamo ostatak.

Primer

Neka je:

s = "amx"
k = 2

Za prvo slovo možemo izabrati:

a
m
x

Ako izaberemo:

a

za drugo slovo ponovo imamo:

aa
am
ax

Na isti način nastaju i sve ostale reči.

Zašto je poredak leksikografski?

Slova obilazimo redom kojim se pojavljuju u stringu s.

Rekurzija zato prirodno generiše reči u leksikografskom redosledu.

Broj reči

Ako string sadrži n slova, a reč ima dužinu k, ukupan broj mogućih reči je:

n^k

#include <iostream>
#include <string>
using namespace std;

// ------------------------------------------------------------
// Rekurzivno generišemo sve reči dužine k.
//
// trenutnaRec
// predstavlja deo reči koji je do sada formiran.
// ------------------------------------------------------------
void generisiReci(
    const string& slova,
    int k,
    string trenutnaRec
) {

    // --------------------------------------------------------
    // Formirana je kompletna reč.
    // --------------------------------------------------------
    if ((int)trenutnaRec.size() == k) {
        cout << trenutnaRec << '\n';
        return;
    }

    // --------------------------------------------------------
    // Na sledeću poziciju možemo staviti
    // bilo koje slovo iz stringa.
    // --------------------------------------------------------
    for (char slovo : slova) {

        generisiReci(
            slova,
            k,
            trenutnaRec + slovo
        );
    }
}

int main() {

    string s;
    int k;

    cin >> s;
    cin >> k;

    generisiReci(s, k, "");

    return 0;
}

Završno objašnjenje

Ovaj zadatak je potpuno isti tip problema kao generisanje svih varijacija sa ponavljanjem.

Jedina razlika je što umesto brojeva koristimo slova.

• brojevi → elementi varijacije
• slova → karakteri reči

Rekurzija gradi reč karakter po karakter, a kada dostignemo dužinu k, reč je spremna za ispis.

Ključna lekcija

Veliki broj zadataka za generisanje može se svesti na:

• izaberi jedan element,
• rekurzivno reši manji problem,
• ponovi za sve moguće izbore.

To je osnovna ideja rekurzivnog pretraživanja i backtracking-a.

Uputstvo — kako razmišljati

Za svaki element skupa postoje samo dve mogućnosti:

• element pripada podskupu,
• element ne pripada podskupu.

Zato za svaki element donosimo jednu od dve odluke.

Ključna ideja

Posmatrajmo element na trenutnoj poziciji.

Rekurzija pravi dve grane:

• ne uzimamo element,
• uzimamo element.

Zatim na isti način obrađujemo sledeći element.

Primer

Neka je skup:

1 2 3

Za element 1 postoje dve mogućnosti:

ne uzmi 1
uzmi 1

Za svaku od tih mogućnosti ponovo odlučujemo za element 2, pa zatim za element 3.

Tako nastaje celo stablo svih podskupova.

Stablo odluka

                 {}
               /    \
             ne      da
             1        1
            / \      / \
           ...      ...

Svaki put od korena do lista predstavlja jedan podskup.

Kada ispisujemo podskup?

Kada obradimo sve elemente skupa.

Tada je niz odluka kompletan i znamo tačno koji elementi pripadaju podskupu.

Koliko ima podskupova?

Za svaki od n elemenata imamo dve mogućnosti:

uzima se
ne uzima se

Ukupan broj podskupova je:

2^n

Pošto primer ne prikazuje prazan skup, njega preskačemo prilikom ispisa.

#include <iostream>
#include <vector>
using namespace std;

// ------------------------------------------------------------
// Rekurzivno generišemo sve podskupove.
//
// pozicija
// označava element o kojem trenutno donosimo odluku.
//
// podskup
// sadrži elemente koje smo do sada izabrali.
// ------------------------------------------------------------
void generisiPodskupove(
    const vector<int>& skup,
    int pozicija,
    vector<int>& podskup
) {

    // --------------------------------------------------------
    // Obrađeni su svi elementi.
    // --------------------------------------------------------
    if (pozicija == (int)skup.size()) {

        // Primer ne traži ispis praznog skupa.
        if (podskup.empty())
            return;

        for (int x : podskup)
            cout << x << " ";

        cout << '\n';
        return;
    }

    // --------------------------------------------------------
    // 1) Trenutni element ne ulazi u podskup.
    // --------------------------------------------------------
    generisiPodskupove(
        skup,
        pozicija + 1,
        podskup
    );

    // --------------------------------------------------------
    // 2) Trenutni element ulazi u podskup.
    // --------------------------------------------------------
    podskup.push_back(
        skup[pozicija]
    );

    generisiPodskupove(
        skup,
        pozicija + 1,
        podskup
    );

    // --------------------------------------------------------
    // Vraćamo stanje pre sledeće grane.
    // --------------------------------------------------------
    podskup.pop_back();
}

int main() {

    int n;
    cin >> n;

    vector<int> skup(n);

    for (int i = 0; i < n; i++) {
        cin >> skup[i];
    }

    vector<int> podskup;

    generisiPodskupove(
        skup,
        0,
        podskup
    );

    return 0;
}

Završno objašnjenje

Za razliku od prethodna dva zadatka, ovde ne biramo jedan od više elemenata.

Umesto toga, za svaki element donosimo odluku:

• uzima se,
• ne uzima se.

Backtracking

Kada dodamo element:

podskup.push_back(...)

nakon završetka te grane moramo da se vratimo u prethodno stanje:

podskup.pop_back()

Upravo to je suština backtracking-a.

Ključna lekcija

Mnogi kombinatorni problemi mogu se svesti na:

• izaberi element,
• ili ga preskoči.

Kada god za svaki objekat postoje dve odluke, veoma često se pojavljuje rekurzivno stablo sa 2^n listova.

Uputstvo — kako razmišljati

Podskupove posmatramo kao rastuće nizove brojeva.

Leksikografski poredak znači da se porede redom, element po element, kao reči u rečniku.

Zato je vrlo važno razumeti da:

• ako je jedan podskup prefiks drugog, kraći je manji,
• ako se razlikuju na nekoj poziciji, manji je onaj sa manjim brojem na toj poziciji.

Ključna ideja

Sledeći podskup tražimo tako što gledamo od desna ka levo.

Postoje tri slučaja:

• ako je podskup prazan, sledeći je {1},
• ako poslednji element može da se poveća, samo ga povećamo za 1,
• ako poslednji element ne može da se poveća, tražimo prvi element zdesna koji može da se poveća i odbacujemo sve elemente desno od njega.

Primer reda podskupova

Za skup {1,2,3,4} redosled počinje ovako:

-
1
1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2
2 3
2 3 4
2 4
3
3 4
4

Zbog toga, posle podskupa 1 2 3 4 5 dolazi 1 2 3 5.

Zašto skidamo sufiks?

Kada povećamo neki element, svi elementi desno od njega više ne mogu da ostanu isti, jer bi novi podskup bio “prevelik”.

Zato biramo najkraći mogući nastavak, a to znači da sve elemente desno od promenjene pozicije brišemo.

Kako pronaći kraj?

Ako nijedan element ne može da se poveća, to znači da smo stigli do leksikografski najvećeg podskupa.

Tada ispisujemo -.

Složenost

U najgorem slučaju prolazimo kroz podskup jednom s desna na levo:

O(k)

gde je k broj elemenata u učitanom podskupu.

#include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <limits>
using namespace std;

// ------------------------------------------------------------
// Određuje sledeći podskup u leksikografskom poretku.
//
// Podskup je predstavljen kao strogo rastući niz.
// Ako postoji sledeći podskup, niz se menja direktno.
// Ako ne postoji, ispisuje se znak '-'.
// ------------------------------------------------------------
void sledeci_podskup(int n, vector<int>& podskup) {

    // --------------------------------------------------------
    // Ako je podskup prazan, sledeći je {1}.
    // --------------------------------------------------------
    if (podskup.empty()) {
        podskup.push_back(1);
        return;
    }

    int k = (int)podskup.size();

    // --------------------------------------------------------
    // Ako možemo da produžimo podskup za još jedan element,
    // u leksikografskom poretku to je sledeći podskup.
    // --------------------------------------------------------
    if (podskup.back() < n) {
        podskup.push_back(podskup.back() + 1);
        return;
    }

    // --------------------------------------------------------
    // U suprotnom tražimo prvi element zdesna
    // koji može da se poveća.
    //
    // Kada ga povećamo, sve elemente desno od njega brišemo.
    // --------------------------------------------------------
    int i = k - 1;

    while (i >= 0 && podskup[i] == n) {
        i--;
    }

    if (i < 0) {
        cout << "-" << '\n';
        return;
    }

    podskup[i]++;

    // --------------------------------------------------------
    // Svi elementi desno od pozicije i se uklanjaju.
    // --------------------------------------------------------
    podskup.resize(i + 1);

    // --------------------------------------------------------
    // Ispis rezultata.
    // --------------------------------------------------------
    for (int x : podskup) {
        cout << x << ' ';
    }
    cout << '\n';
}

int main() {

    int n;
    cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    // --------------------------------------------------------
    // Učitavamo celu narednu liniju.
    // Ako je linija prazna, to znači da je učitan prazan podskup.
    // --------------------------------------------------------
    string linija;
    getline(cin, linija);

    vector<int> podskup;
    stringstream ss(linija);
    int broj;

    while (ss >> broj) {
        podskup.push_back(broj);
    }

    sledeci_podskup(n, podskup);

    return 0;
}

Završno objašnjenje

Najvažnije je da podskup ne posmatramo kao skup, već kao niz elemenata u rastućem poretku.

Tada naredni podskup dobijamo isto kao “sledeću reč” u rečniku:

• krećemo od desne strane,
• tražimo prvi element koji može da poraste,
• povećamo ga,
• i brišemo sve što je desno od njega.

Ako ne postoji nijedan element koji može da se poveća, podskup je već poslednji.

Ključna lekcija

Kod leksikografskog poretka često je dovoljno da posmatramo samo prvu poziciju na kojoj dolazi do promene.

Ovde je to upravo element koji menjamo s desna na levo.