Problemi se često mogu rešiti iscrpnom pretragom (grubom silom), što podrazumeva da se ispitaju svi mogući kandidati za rešenja. Preduslov za to je da umemo sve te kandidate da nabrojimo. Iako u realnim primenama prostor potencijalnih rešenja može imati različitu strukturu, pokazuje se da je u velikom broju slučaja to prostor određenih klasičnih kombinatornih objekata: svih podskupova nekog konačnog skupa, svih varijacija (sa ili bez ponavljanja), svih kombinacija (sa ili bez ponavljanja), svih permutacija, svih particija i slično. U ovom poglavlju ćemo proučiti mehanizme njihovog sistematičnog generisanja. Naglasimo da po pravilu ovakvih objekata ima eksponencijalno mnogo u odnosu na veličinu ulaza, tako da su svi algoritmi praktično neupotrebljivi osim za veoma male dimenzije ulaza.
Objekti se obično predstavljaju \(n\)-torkama brojeva, pri čemu se isti objekti mogu torkama modelovati na različite načine. Na primer, svaki podskup skupa \(\{a_0, \ldots, a_{n-1}\}\) se može predstaviti konačnim nizom indeksa elemenata koji mu pripadaju. Da bi svaki podskup bio jedinstveno predstavljen, potrebno je da taj niz bude kanonizovan (na primer, uređen strogo rastući). Na primer, torka \((0, 2, 3)\) jednoznačno određuje podskup \(\{a_0, a_2, a_3\}\). Drugi način da se podskupovi predstave su \(n\)-torke logičkih vrednosti ili vrednosti 0-1. Na primer, ako je \(n=6\), i ako pretpostavimo da se bitovi čitaju sleva nadesno, tada torka \(101100\) označava skup \(\{a_0, a_2, a_3\}\).
Svi objekti se obično mogu predstaviti drvetom i to drvo odgovara procesu njihovog generisanja tj. obilaska (ono se ne pravi eksplicitno, u memoriji, ali nam pomaže da razumemo i organizujemo postupak pretrage). Obilazak drveta se najjednostavnije izvodi u dubinu (često rekurzivno). Za prvu navedenu reprezentaciju podskupova drvo je dato na slici 18. Svaki čvor drveta odgovara jednom podskupu, pri čemu se odgovarajuća torka očitava na granama puta koji vodi od korena do tog čvora.
Za drugu navedenu reprezentaciju podskupova drvo je dato na slici 19. Na početku se bira da li će element \(a_0\) biti uključen u podskup, na narednom nivou da li će biti uključen element \(a_1\), zatim element \(a_2\) i tako dalje. Samo listovi drveta u kojima je za svaki element doneta odluka da li pripada ili ne pripada podskupu, odgovaraju podskupovima, pri čemu se odgovarajuća torka logičkih vrednosti očitava na granama puta koji vodi od korena do tog čvora.
Primetimo da oba drveta sadrže \(2^n\) čvorova kojima se predstavljaju podskupovi (u prvom slučaju su to svi čvorovi drveta, a u drugom samo listovi).
Prilikom generisanja objekata često je poželjno ređati ih određenim redom. S obzirom na to to da se svi kombinatorni objekti predstavljaju određenim torkama (konačnim nizovima), prirodan poredak među njima je leksikografski poredak (koji se koristi za utvrđivanje redosleda reči u rečniku). Podsetimo se, torka \(a_0\ldots a_{m-1}\) leksikografski prethodi torci \(b_0\ldots b_{n-1}\) akko postoji neki indeks \(i\) takav da za svako \(0 \leq j < i\) važi \(a_j = b_j\) i važi ili da je \(a_i < b_i\) ili da je \(i = m < n\). Na primer važi da je \(11 < 112 < 221\) (ovde je \(i=2\), a zatim \(i=0\)).
Na primer, ako podskupove skupa \(\{1, 2, 3\}\) predstavimo na prvi način, torkama u kojima su elementi uređeni rastuće, leksikografski poredak bi bio \(\emptyset\), \(\{1\}\), \(\{1, 2\}\), \(\{1, 2, 3\}\), \(\{1, 3\}\), \(\{2\}\), \(\{2, 3\}\), \(\{3\}\). Ako bismo ih predstavljali na drugi način, torkama u kojima se nulama i jedinicama određuje da li je neki element uključen u podskup, leksikografski redosled bi bio: 000 (\(\emptyset\)), 001 (\(\{3\}\)), 010(\(\{2\}\)), 011(\(\{2, 3\}\)), 100(\(\{1\}\)), 101(\(\{1,3\}\)), 110(\(\{1,2\}\)) i 111(\(\{1,2,3\}\)).
U nastavku će biti prikazano kako je moguće nabrojati sve objekte koji imaju neku zadatu kombinatornu strukturu. U većini zadataka moguće je razmatrati dve vrste rešenja. Jedna grupa rešenja je zasnovana na rekurzivnom postupku nabrajanja objekata, dok je druga grupa rešenja zasnovana na pronalaženju narednog kombinatornog objekta u odnosu na neki zadati redosled (najčešće leksikorafski).
Napisati program koji određuje podskup skupa brojeva \(\{1, \ldots, n\}\) koji u leksikografskom redosledu sledi neposredno iza datog podskupa. Podskupovi su zadati u obliku strogo rastuće sortiranih nizova.
Prva linija sadrži broj \(n\) (\(1 \leq n \leq 100\)), a naredna linija sadrži podskup čiji su elementi zadati sortirano rastuće, razdvojeni po jednim razmakom.
Na standardni izlaz u jednoj liniji ispisati elemente traženog podskupa tj. - ako je učitani podskup leksikografski najveći.
5 1 2 3 4 5
1 2 3 5
5 5
-
Napišimo, na primer, leksikografski uređen spisak svih podskupova skupa brojeva od 1 do 4.
-, 1, 12, 123, 1234, 124, 13, 134, 14, 2, 23, 234, 24, 3, 34, 4
Možemo primetiti da postoje dva načina da se dođe do narednog podskupa. Analizirajmo ove skupove u istom redosledu, grupisane u kolone na osnovu broja elemenata.
- 1 12 123 1234 124 13 134 14 2 23 234 24 3 34 4
Jedan način je proširivanje kada se naredni podskup dobija dodavanjem nekog elementa u prethodni. To su koraci u prethodnoj tabeli kod kojih se prelazi iz jedne u narednu kolonu. Da bi dobijeni podskup sledio neposredno iza prethodnog u leksikografskom redosledu, dodati element podskupu mora biti najmanji mogući. Pošto je svaki podskup sortiran, element mora biti za jedan veći od poslednjeg elementa podskupa koji se proširuje (izuzetak je prazan skup, koji se proširuje elementom 1). Jedini slučaj kada proširivanje nije moguće je kada je poslednji element podskupa najveći mogući (u našem primeru to je 4).
Drugi način je skraćivanje kada se naredni element dobija uklanjanjem nekih elemenata iz podskupa i izmenom preostalih elemenata. To su koraci u prethodnoj tabeli kod kojih se prelazi sa kraja jedne u narednu vrstu. U ovom slučaju skraćivanje funkcioniše tako što se iz podskupa izbaci završni najveći element, a zatim se najveći od preostalih elemenata uveća za 1 (on ne može biti najveći, jer su elementi unutar svakog podskupa strogo rastući). Ako nakon izbacivanja najvećeg elementa ostane prazan skup, naredna kombinacija ne postoji.
Podskupove možemo predstaviti dinamičkim nizom koji nam omogućva da elemente dodajemo i uklaljamo sa desnog kraja. U jeziku C++ možemo upotrebiti vektor (tj. kolekciju vector).
// na osnovu datog podskupa skupa {1, ..., n} određuje
// leksikografski naredni podskup i vraca da li on postoji
bool sledeciPodskup(vector<int>& podskup, int n) {
// specijalni slučaj proširivanja praznog skupa
if (podskup.empty()) {
podskup.push_back(1);
// podskup je uspešno pronađen
return true;
}
// proširivanje
if (podskup.back() < n) {
// u podskup dodajemo element koji je za 1 veći od
// trenutno najvećeg elementa
podskup.push_back(podskup.back() + 1);
// podskup je uspešno pronađen
return true;
}
// skraćivanje
// uklanjamo poslednji najveći element
podskup.pop_back();
// ako nema preostalih elemenata ne postoji naredni podskup
if (podskup.empty())
return false;
// najveći od preostalih elemenata uvećavamo za 1
podskup.back()++;
// podskup je uspešno pronađen
return true;
}#include <iostream>
#include <vector>
using namespace std;
// na osnovu datog podskupa skupa {1, ..., n} određuje
// leksikografski naredni podskup i vraca da li on postoji
bool sledeciPodskup(vector<int>& podskup, int n) {
// specijalni slučaj proširivanja praznog skupa
if (podskup.empty()) {
podskup.push_back(1);
// podskup je uspešno pronađen
return true;
}
// proširivanje
if (podskup.back() < n) {
// u podskup dodajemo element koji je za 1 veći od
// trenutno najvećeg elementa
podskup.push_back(podskup.back() + 1);
// podskup je uspešno pronađen
return true;
}
// skraćivanje
// uklanjamo poslednji najveći element
podskup.pop_back();
// ako nema preostalih elemenata ne postoji naredni podskup
if (podskup.empty())
return false;
// najveći od preostalih elemenata uvećavamo za 1
podskup.back()++;
// podskup je uspešno pronađen
return true;
}
int main() {
int n;
cin >> n;
vector<int> podskup;
int x;
while (cin >> x)
podskup.push_back(x);
if (sledeciPodskup(podskup, n)) {
for (int x : podskup)
cout << x << " ";
cout << endl;
} else {
cout << "-" << endl;
}
return 0;
}Podskupove možemo čuvati i u okviru niza koji je unapred alociran tako da može da smesti elemente najvećeg podskupa (onog koji ima tačno \(n\) elemenata). U tom slučaju je neophodno da održavamo i promenljivu u kojoj beležimo broj elemenata podskupa. Pošto se ona menja u funkciji koja određuje naredni podskup, potrebno je preneti je po referenci.
// na osnovu datog podskupa skupa {1, ..., n} određuje
// leksikografski naredni podskup i vraća da on postoji.
// Tekući podskup je smešten u nizu dužine k
bool sledeciPodskup(int podskup[], int& k, int n) {
// specijalni slučaj proširivanja praznog skupa
if (k == 0) {
podskup[k++] = 1;
return true;
}
// proširivanje
if (podskup[k-1] < n) {
// u podskup dodajemo element koji je za 1 veći od
// trenutno najvećeg elementa
podskup[k] = podskup[k-1] + 1;
k++;
return true;
}
// skraćivanje
// izbacujemo najveći element iz podskupa
k--;
// ako nema preostalih elemenata, naredni podskup ne postoji
if (k == 0)
return false;
// najveći od preostalih elemenata uvećavamo za 1
podskup[k-1]++;
return true;
}#include <iostream>
using namespace std;
// na osnovu datog podskupa skupa {1, ..., n} određuje
// leksikografski naredni podskup i vraća da on postoji.
// Tekući podskup je smešten u nizu dužine k
bool sledeciPodskup(int podskup[], int& k, int n) {
// specijalni slučaj proširivanja praznog skupa
if (k == 0) {
podskup[k++] = 1;
return true;
}
// proširivanje
if (podskup[k-1] < n) {
// u podskup dodajemo element koji je za 1 veći od
// trenutno najvećeg elementa
podskup[k] = podskup[k-1] + 1;
k++;
return true;
}
// skraćivanje
// izbacujemo najveći element iz podskupa
k--;
// ako nema preostalih elemenata, naredni podskup ne postoji
if (k == 0)
return false;
// najveći od preostalih elemenata uvećavamo za 1
podskup[k-1]++;
return true;
}
int main() {
int n;
cin >> n;
// elementi podskupa
const int MAX = 100;
int podskup[MAX];
// broj elemenata podskupa
int k = 0;
// ucitavamo elemente datog podskupa
int x;
while (cin >> x)
podskup[k++] = x;
// pokusavamo da pronadjemo naredni podskup
if (sledeciPodskup(podskup, k, n)) {
// ako postoji, ispisujemo ga
for (int i = 0; i < k; i++)
cout << podskup[i] << " ";
cout << endl;
} else
// naredni podskup ne postoji
cout << "-" << endl;
return 0;
}Napisati program koji ispisuje sve podskupove datog skupa.
Sa standardnog ulaza se učitava broj \(n\) (važi \(3 \leq n \leq 10\)), a zatim \(n\) prirodnih brojeva, rastuće sortiranih, razdvojenih po jednim razmakom.
Na standardni izlaz ispisati sve podskupove učitanog skupa brojeva, svaki u posebnom redu, sa elementima razdvojenim jednim razmakom. Prvo se ređaju podskupovi u kojima prvi element nije uključen, a zatim oni u kojima jeste. U svakoj od te dve grupe, prvo se ispisuju podskupovi u kojima drugi element nije uključen, a zatim oni gde jeste i tako dalje.
3 1 2 3
3 2 2 3 1 1 3 1 2 1 2 3
Generisanje svih podskupova odgovara generisanju svih varijacija dužine \(n\) od nula i jedinica (svaki element je ili uključen ili isključen). Poredak opisan u postavci zadatka ukazuje na to da podskupovi treba da budu uređeni leksikografski, u odnosu na njihovu reprezentaciju u obliku varijacija.
Opišimo induktivno-rekurzivnu konstrukciju funkcije koja generiše sve podskupove skupa \(S\).
Ako je skup \(S\) prazan, onda je jedini njegov podskup prazan.
Ako skup \(S\) nije prazan, onda se može razložiti na neki element \(x\) i skup \(S' = S \setminus x\) dobijen kada se taj element izbaci iz polaznog skupa. Pošto je skup \(S'\) manji od skupa \(S\), njegovi se podskupovi mogu odrediti rekurzivno. Svi podskupovi polaznog skupa \(S\) su onda oni koji su određeni za manji skup \(S'\), kao i svi oni koji se od njih dobijaju dodavanjem izdvojenog elementa \(x\).
Prethodnu konstrukciju nije ekonomično programski realizovati, jer se pretpostavlja da rezultat rada funkcije predstavlja skup svih podskupova skupa. Umesto takve funkcije definisaćemo proceduru koja neće istovremeno čuvati i vraćati sve podskupove već samo jedan po jedan nabrojati i obraditi (u našem slučaju samo ispisati).
Do rešenja se može doći tako što se u rekurzivnoj funkciji prosleđuje neki podsup \(P\) skupa \(\{a_0, \ldots, a_{i-1}\}\) i koji ona na sve moguće načine proširuje elementima skupa \(\{a_i, \ldots, a_{n-1}\}\).
Ako je skup \(\{a_i, \ldots, a_{n-1}\}\) prazan (ako je \(i=n\)) tada je podskup \(P\) kompletno formiran i obrađuje se (tj. ispisuje).
U suprotnom razmatramo element \(a_i\) i dve mogućnosti: da taj element bude izostavljen iz podsupa i mogućnost da taj element bude dodat u podskup \(P\). U oba slučaja nastavljamo rekurzivno proširivanje skupa \(P\) (prvo neproširenog, a zatim i proširenog elementom \(a_i\)) elementima skupa \(\{a_{i+1}, \ldots, a_{n-1}\}\).
Inicijalno je \(i=0\), a podskup je prazan (prazan skup je, zaista, jedini podskup praznog supa \(\{a_0, \ldots, a_{i-1}\}\) i on se na sve moguće načine proširuje elementima skupa \(\{a_i, \ldots, a_{n-1}\} = \{a_0, \ldots, a_{n-1}\}\)).
Iako mnogi savremeni jezici pružaju tip za reprezentovanje skupova, implementacija je jednostavnija i efikasnija ako se elementi skupa čuvaju u nizu. Da bismo izbegli potrebu za produžavanjem i skraćivanjem niza i korišćenjem dinamičkih nizova, lista ili vektra, niz možemo alocirati na maksimalnu moguću dužinu (broj elemenata polaznog skupa) i paralelno sa nizom možemo održavati broj elemenata podskupa koji je trenutno smešten u niz (on je skoro uvek strogo manji od dužine niza).
Dakle, definišemo rekurzivnu funkciju koja na svakom narednom nivou rekurzije obrađuje naredni element polaznog skupa (predstavljenog nizom), sve dok se ne iscrpe svi elementi. U prvom slučaju taj element ne dodaje u rezultujući podskup (takođe predstavljen nizom, koji prosleđujemo kao dodatni parametar) i prelazi na naredni nivo rekurzije, a u drugom ga dodaje na kraj trenutnog rezultujućeg podskupa i prelazi na naredni nivo rekurzije. Kada se ceo polazni niz iscrpi (kada je dubina rekurzije jednaka dužini polaznog niza), tada se trenutno akumulirani podskup obrađuje tj. ispisuje.
Rad rekurzivne funkcije odgovara slici 19.
// procedura određuje i obrađuje sve moguće skupove koji se
// dobijaju tako što se na elemente prosleđenog podskupa p
// dužine j, dodaju podskupovi prosleđenog skupa smeštenog u
// nizu a, od pozicije i nadalje
void obradi_sve_podskupove(const vector<int>& a, int i,
vector<int>& p, int j) {
// skup preostalih elemenata u nizu a koji se mogu ubaciti u
// podskup je prazan
if (i == a.size())
// obrađujemo formirani podskup
obradi(p, j);
else {
// element na poziciji i ne uključujemo u podskup
obradi_sve_podskupove(a, i + 1, p, j);
// element na poziciji i uključujemo u podskup
p[j] = a[i];
obradi_sve_podskupove(a, i + 1, p, j + 1);
}
}
void obradi_sve_podskupove(const vector<int>& a) {
// podskup je na početku prazan, i u njega potencijalno
// dodajemo sve elemente skupa a od pozicije 0 nadalje
vector<int> p(a.size());
obradi_sve_podskupove(a, 0, p, 0);
}#include <iostream>
#include <vector>
using namespace std;
// ispis prvih n elemenata niza a
void obradi(const vector<int>& a, int n) {
for (int k = 0; k < n; k++)
cout << a[k] << " ";
cout << endl;
}
// procedura određuje i obrađuje sve moguće skupove koji se
// dobijaju tako što se na elemente prosleđenog podskupa p
// dužine j, dodaju podskupovi prosleđenog skupa smeštenog u
// nizu a, od pozicije i nadalje
void obradi_sve_podskupove(const vector<int>& a, int i,
vector<int>& p, int j) {
// skup preostalih elemenata u nizu a koji se mogu ubaciti u
// podskup je prazan
if (i == a.size())
// obrađujemo formirani podskup
obradi(p, j);
else {
// element na poziciji i ne uključujemo u podskup
obradi_sve_podskupove(a, i + 1, p, j);
// element na poziciji i uključujemo u podskup
p[j] = a[i];
obradi_sve_podskupove(a, i + 1, p, j + 1);
}
}
void obradi_sve_podskupove(const vector<int>& a) {
// podskup je na početku prazan, i u njega potencijalno
// dodajemo sve elemente skupa a od pozicije 0 nadalje
vector<int> p(a.size());
obradi_sve_podskupove(a, 0, p, 0);
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
obradi_sve_podskupove(a);
return 0;
}U implementaciji možemo koristiti i bibliotečke kolekcije za reprezentovanje niza elemenata. Međutim, treba biti veoma obazriv jer je moguće da se tokom rekurzije grade novi nizovi i kopiraju elementi, što znatno utiče na efikasnost. Naredna implementacija je zbog toga veoma loša.
// procedura određuje i obrađuje sve moguće skupove koji se
// dobijaju tako što se na elemente prosleđenog podskupa
// dodaju podskupovi prosleđenog skupa
void obradiSvePodskupove(const vector<int>& skup,
const vector<int>& podskup) {
// skup je prazan
if (skup.size() == 0)
// na prosleđeni podskup možemo dodati samo prazan skup
obradi(podskup);
else {
// izdvajamo i uklanjamo proizvoljan element skupa
int x = skup.back();
vector<int> smanjenSkup = skup;
smanjenSkup.pop_back();
// u podskup dodajemo sve podskupove skupa bez izdvojenog
// elementa
vector<int> podskupBez = podskup;
obradiSvePodskupove(smanjenSkup, podskupBez);
// u podskup uključujemo izdvojeni element i zatim sve
// podskupove skupa bez izdvojenog elementa
vector<int> podskupSa = podskup;
podskupSa.push_back(x);
obradiSvePodskupove(smanjenSkup, podskupSa);
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// ispis elemenata niza a
void obradi(const vector<int>& a) {
for (int i = 0; i < a.size(); i++)
cout << a[i] << " ";
cout << endl;
}
// procedura određuje i obrađuje sve moguće skupove koji se
// dobijaju tako što se na elemente prosleđenog podskupa
// dodaju podskupovi prosleđenog skupa
void obradiSvePodskupove(const vector<int>& skup,
const vector<int>& podskup) {
// skup je prazan
if (skup.size() == 0)
// na prosleđeni podskup možemo dodati samo prazan skup
obradi(podskup);
else {
// izdvajamo i uklanjamo proizvoljan element skupa
int x = skup.back();
vector<int> smanjenSkup = skup;
smanjenSkup.pop_back();
// u podskup dodajemo sve podskupove skupa bez izdvojenog
// elementa
vector<int> podskupBez = podskup;
obradiSvePodskupove(smanjenSkup, podskupBez);
// u podskup uključujemo izdvojeni element i zatim sve
// podskupove skupa bez izdvojenog elementa
vector<int> podskupSa = podskup;
podskupSa.push_back(x);
obradiSvePodskupove(smanjenSkup, podskupSa);
}
}
void obradiSvePodskupove(const vector<int>& skup) {
// pošto elementi iz skupa u podskup prebacuju sa desnog kraja, da
// bismo dobili traženi redosled podskupa, potrebno je da obrnemo
// redosled elemenata skupa
vector<int> skupObratno = skup;
reverse(begin(skupObratno), end(skupObratno));
// krećemo od praznog podskupa
vector<int> podskup;
// prazan skup proširujemo svim podskupovima datog skupa
obradiSvePodskupove(skupObratno, podskup);
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
obradiSvePodskupove(a);
return 0;
}Moguće je napraviti rešenje koje koristi bibliotečke kolekcija podataka, a ujedno ne vrši njihovo kopiranje i dovoljno je efikasno. U implementaciji se koriste dva niza (jedan za skup, drugi za podskup) koji se tokom rada algoritma menjaju. Nizovi će se menjati dodavanjem i ukljanjanjem elemenata sa kraja. Zato je pre početka funkcije neohpodno obrnuti redosled elemenata u nizu (da bi se na kraju prvo našli početni elementi niza).
U implementacijama koje menjaju nizove često je važno osigurati da se na kraju tela rekurzivne funkcije stanje nizova vrati na isto stanje kakvo je bilo na ulasku u funkciju, jer se time garantuje da rekurzivni poziv neće modifikovati nizove koji su mu predati kao parametri (što koristimo kada se oslanjamo na to da će i nakon prvog i nakon drugog rekurzivnog poziva skup i podskup biti isti kakvi su bili i pre tog rekurzivnog poziva).
// procedura određuje i obrađuje sve moguće skupove koji se
// dobijaju tako što se na elemente prosleđenog podskupa dodaju
// podskupovi prosleđenog skupa
void obradiSvePodskupove(vector<int>& skup,
vector<int>& podskup) {
// skup je prazan
if (skup.size() == 0)
// na prosleđeni podskup možemo dodati samo prazan skup
obradi(podskup);
else {
// izdvajamo i uklanjamo proizvoljan element skupa
int x = skup.back();
skup.pop_back();
// u podskup dodajemo sve podskupove skupa bez izdvojenog
// elementa
obradiSvePodskupove(skup, podskup);
// u podskup uključujemo izdvojeni element i zatim sve
// podskupove skupa bez izdvojenog elementa
podskup.push_back(x);
obradiSvePodskupove(skup, podskup);
// vraćamo skup i podskup u početno stanje
podskup.pop_back();
skup.push_back(x);
}
}
void obradiSvePodskupove(vector<int>& skup) {
// pošto elementi iz skupa u podskup prebacuju sa desnog
// kraja, da bismo dobili traženi redosled podskupa,
// potrebno je da obrnemo redosled elemenata skupa
vector<int> skupObratno = skup;
reverse(begin(skupObratno), end(skupObratno));
// krećemo od praznog podskupa
vector<int> podskup;
// efikasnosti radi rezervišemo potrebnu memoriju za
// najveći podskup
podskup.reserve(skup.size());
// prazan skup proširujemo svim podskupovima datog skupa
obradiSvePodskupove(skupObratno, podskup);
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// ispis vektora
void obradi(const vector<int>& a) {
for (int i = 0; i < a.size(); i++)
cout << a[i] << " ";
cout << endl;
}
// procedura određuje i obrađuje sve moguće skupove koji se
// dobijaju tako što se na elemente prosleđenog podskupa dodaju
// podskupovi prosleđenog skupa
void obradiSvePodskupove(vector<int>& skup,
vector<int>& podskup) {
// skup je prazan
if (skup.size() == 0)
// na prosleđeni podskup možemo dodati samo prazan skup
obradi(podskup);
else {
// izdvajamo i uklanjamo proizvoljan element skupa
int x = skup.back();
skup.pop_back();
// u podskup dodajemo sve podskupove skupa bez izdvojenog
// elementa
obradiSvePodskupove(skup, podskup);
// u podskup uključujemo izdvojeni element i zatim sve
// podskupove skupa bez izdvojenog elementa
podskup.push_back(x);
obradiSvePodskupove(skup, podskup);
// vraćamo skup i podskup u početno stanje
podskup.pop_back();
skup.push_back(x);
}
}
void obradiSvePodskupove(vector<int>& skup) {
// pošto elementi iz skupa u podskup prebacuju sa desnog
// kraja, da bismo dobili traženi redosled podskupa,
// potrebno je da obrnemo redosled elemenata skupa
vector<int> skupObratno = skup;
reverse(begin(skupObratno), end(skupObratno));
// krećemo od praznog podskupa
vector<int> podskup;
// efikasnosti radi rezervišemo potrebnu memoriju za
// najveći podskup
podskup.reserve(skup.size());
// prazan skup proširujemo svim podskupovima datog skupa
obradiSvePodskupove(skupObratno, podskup);
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
obradiSvePodskupove(a);
return 0;
}Jedno rešenje je da se u posebnom nizu logičkih vrednosti nabrajaju sve varijacije skupa tačno-netačno. Svaka takva varijacija odgovara jednom podskupu, tako što se u podskup uključuju elementi sa onih pozicija na kojima je je vrednost tačno. Varijacije nabrajamo korišćenjem funkcije za određivanje sledeće varijacije.
void obradiSvePodskupove(const vector<int>& a) {
vector<bool> v(a.size(), false);
do {
obradi(v, a);
} while (sledecaVarijacija(v));
}#include <iostream>
#include <vector>
using namespace std;
void obradi(const vector<bool>& v, const vector<int>& a) {
for (int i = 0; i < v.size(); i++)
if (v[i])
cout << a[i] << " ";
cout << endl;
}
bool sledecaVarijacija(vector<bool>& v) {
int i = v.size() - 1;
while (i >= 0 && v[i])
v[i--] = false;
if (i < 0) return false;
v[i] = true;
return true;
}
void obradiSvePodskupove(const vector<int>& a) {
vector<bool> v(a.size(), false);
do {
obradi(v, a);
} while (sledecaVarijacija(v));
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
obradiSvePodskupove(a);
return 0;
}Napisati program koji određuje narednu varijaciju dužine \(k\) skupa \(\{1, \ldots, n\}\) u leksikografskom poretku.
Prva linija standardnog ulaza sadrži broj \(k\) (\(1 \leq k \leq 100\)), a druga broj \(n\) (\(1 \leq n \leq 100\)). U trećoj liniji se nalazi varijacija opisana brojevima razdvojenim po jednim razmakom.
Na standardni izlaz ispisati sledeću varijaciju u leksikografskom poretku, ako ona postoji, ili -, ako je učitana varijacija leksikografski maksimalna.
5 4 1 1 2 3 4
1 1 2 4 1
Sledeća varijacija u leksikografskom poretku se može generisati tako što se uveća poslednji broj u varijaciji koji se može uvećati, i što se nakon uvećavanja svi brojevi iza uvećanog broja postave na \(1\). Pozicija na kojoj se broj uvećava naziva se prelomna tačka (engl. turning point). Na primer, ako nabrajamo varijacije skupa \(\{1, 2, 3\}\) dužine \(5\) naredna varijacija za varijaciju \(21332\) je \(21333\) (prelomna tačka je pozicija \(4\), koja je poslednja pozicija u nizu), dok je njoj naredna varijacija \(22111\) (prelomna tačka je pozicija \(1\) na kojoj se nalazio element \(1\)). Niz \(33333\) nema prelomnu tačku, pa samim tim ni leksikografski sledeću varijaciju.
Jedan način implementacije je da prelomnu tačku nađemo linearnom pretragom od kraja niza, ako prelomna tačka postoji da uvećamo element i da od sledeće pozicije do kraja niz popunimo jedinicama. Međutim, te dve faze možemo objediniti. Varijaciju obilazimo od kraja postavljajući na 1 svaki element u varijaciji koji je jednak broju \(n\). Ako se zaustavimo pre nego što smo stigli do kraja niza, znači da smo pronašli element koji se može uvećati i uvećavamo ga. U suprotnom je varijacija imala sve elemente jednake \(n\) i bila je maksimalna u leksikografskom redosledu.
bool sledecaVarijacija(int n, vector<int>& varijacija) {
// od kraja varijacije tražimo prvi element koji se moze
// povecati
int i;
int k = varijacija.size();
for (i = k-1; i >= 0 && varijacija[i] == n; i--)
varijacija[i] = 1;
// svi elementi su jednaki n, pa ne postoji naredna
// varijacija
if (i < 0) return false;
// uvecavamo element koji je moguće uvecati
varijacija[i]++;
return true;
}#include <iostream>
#include <vector>
using namespace std;
void ispisi(const vector<int>& varijacija) {
for (int x : varijacija)
cout << x << " ";
cout << endl;
}
bool sledecaVarijacija(int n, vector<int>& varijacija) {
// od kraja varijacije tražimo prvi element koji se moze
// povecati
int i;
int k = varijacija.size();
for (i = k-1; i >= 0 && varijacija[i] == n; i--)
varijacija[i] = 1;
// svi elementi su jednaki n, pa ne postoji naredna
// varijacija
if (i < 0) return false;
// uvecavamo element koji je moguće uvecati
varijacija[i]++;
return true;
}
int main() {
int k, n;
cin >> k >> n;
vector<int> varijacija(k);
for (int i = 0; i < k; i++)
cin >> varijacija[i];
if (sledecaVarijacija(n, varijacija))
ispisi(varijacija);
else
cout << "-" << endl;
return 0;
}Napiši program koji određuje sve varijacije sa ponavljanjem dužine \(k\) skupa \(\{1, \ldots, n\}\).
Sa standardnog ulaza se učitava broj \(n\) (\(1 \leq n \leq 5\)) i u narednoj liniji broj \(k\) (\(1 \leq k \leq 5\)).
Na standardni izlaz ispisati sve varijacije, sortirane leksikografski.
2 3
1 1 1 1 1 2 1 2 1 1 2 2 2 1 1 2 1 2 2 2 1 2 2 2
Varijacije se mogu nabrojati induktivno rekurzivnom konstrukcijom.
Jedina varijacija dužine nula je prazna.
Sve varijacije dužine \(k\) se mogu dobiti tako što se na prvo mesto upiše bilo koji od brojeva od \(1\) do \(n\), a zatim se preostala mesta dopune svim varijacijama dužine \(k-1\).
Recimo i da je moguće na poslednje mesto postavljati jedan po jedan broj od \(1\) do \(n\), a zatim rekurzivno popunjavati prefiks, no time bi redosled varijacija bio drugačiji od traženog.
Umesto da definišemo funkciju koja vraća kolekciju varijacija, definisaćemo rekurzivnu proceduru koja prima niz kome su popunjeni svi elementi osim poslednjih \(k\), i koji će na sve moguće načine dopunjavati varijacijama dužine \(k\) (koja će se smanjivati kroz rekurzivne pozive). Dakle, nakon popunjenog dela niza postavljamo jednu po jednu vrednost od \(1\) do \(n\) i zatim rekurzivno pozivamo proceduru da popuni ostatak niza (time što smanjujemo dužinu \(k\) i time prelazimo na narednu poziciju).
Da bismo izbegli potrebu za dinamičkim proširivanjem nizova unapred ćemo alocirati niz dužine \(k\), a onda ćemo mu u rekurziji popunjavati jednu po jednu poziciju (tekuća pozicija se može odrediti kao razlika između dužine niza i tekuće vrednosti broja \(k\)).
// Sve varijacije duzine k elemenata skupa {1, ..., n}
// Data varijacija duzine varijacije.size() - k se
// dopunjuje svim mogucim varijacijama duzine k skupa
// {1, ..., n} i sve tako dobijene varijacije se
// obradjuju funkcijom obradi
void obradiSveVarijacije(int k, int n,
vector<int>& varijacija) {
// k je 0, pa je jedina varijacija duzine nula prazna i
// njenim dodavanjem na polazni niz on se ne menja
if (k == 0)
obradi(varijacija);
else
// na tekucu poziciju postavljamo sve moguce vrednosti
// od 1 do n i dobijeni niz onda rekurzivno proširujemo
for (int nn = 1; nn <= n; nn++) {
varijacija[varijacija.size() - k] = nn;
obradiSveVarijacije(k-1, n, varijacija);
}
}
// sve varijacije duzine k skupa {1, ..., n}
void obradiSveVarijacije(int k, int n) {
vector<int> varijacija(k);
obradiSveVarijacije(k, n, varijacija);
}#include <iostream>
#include <vector>
using namespace std;
// ispisuje tekucu varijaciju na standardni izlaz
void obradi(const vector<int>& varijacija) {
for (int x : varijacija)
cout << x << " ";
cout << endl;
}
// Sve varijacije duzine k elemenata skupa {1, ..., n}
// Data varijacija duzine varijacije.size() - k se
// dopunjuje svim mogucim varijacijama duzine k skupa
// {1, ..., n} i sve tako dobijene varijacije se
// obradjuju funkcijom obradi
void obradiSveVarijacije(int k, int n,
vector<int>& varijacija) {
// k je 0, pa je jedina varijacija duzine nula prazna i
// njenim dodavanjem na polazni niz on se ne menja
if (k == 0)
obradi(varijacija);
else
// na tekucu poziciju postavljamo sve moguce vrednosti
// od 1 do n i dobijeni niz onda rekurzivno proširujemo
for (int nn = 1; nn <= n; nn++) {
varijacija[varijacija.size() - k] = nn;
obradiSveVarijacije(k-1, n, varijacija);
}
}
// sve varijacije duzine k skupa {1, ..., n}
void obradiSveVarijacije(int k, int n) {
vector<int> varijacija(k);
obradiSveVarijacije(k, n, varijacija);
}
int main() {
int n, k;
cin >> n >> k;
obradiSveVarijacije(k, n);
return 0;
}Druga mogućnost je da se krene od leksikografski najmanje varijacije (to je varijacija \(\underbrace{11\ldots 11}_{k}\)) i da se korišćenjem funkcije opisane u zadatku [Sledeća varijacija] određuje naredna varijacija date varijacije u odnosu na leksikografski redosled, sve dok takva postoji.
void obradiSveVarijacije(int k, int n) {
// krećemo od varijacije 11...11
// ona je leksikografski najmanja
vector<int> varijacija(k, 1);
// obradjujemo redom varijacije dok god postoji
// leksikografski sledeca
do {
obradi(varijacija);
} while(sledecaVarijacija(n, varijacija));
}#include <iostream>
#include <vector>
using namespace std;
// ispisuje tekucu varijaciju na standardni izlaz
void obradi(const vector<int>& varijacija) {
for (int x : varijacija)
cout << x << " ";
cout << endl;
}
bool sledecaVarijacija(int n,
vector<int>& varijacija) {
// od kraja varijacije tražimo prvi element koji se moze povecati
int i;
int k = varijacija.size();
for (i = k-1; i >= 0 && varijacija[i] == n; i--)
varijacija[i] = 1;
// svi elementi su jednaki n - ne postoji naredna varijacija
if (i < 0) return false;
// uvecavamo element koji je moguće uvecati
varijacija[i]++;
return true;
}
void obradiSveVarijacije(int k, int n) {
// krećemo od varijacije 11...11
// ona je leksikografski najmanja
vector<int> varijacija(k, 1);
// obradjujemo redom varijacije dok god postoji
// leksikografski sledeca
do {
obradi(varijacija);
} while(sledecaVarijacija(n, varijacija));
}
int main() {
int n, k;
cin >> n >> k;
obradiSveVarijacije(k, n);
return 0;
}Kombinacije dužine \(k\) od \(n\) elemenata podrazumevaju da se vrši odabir \(k\) elemenata skupa \(\{1, \ldots, n\}\), slično kao što se, na primer, u igri loto bira 7 od 39 kuglica. Napiši program koji za date vrednosti \(k\) i \(n\) nabraja i ispisuje sve kombinacije, poređane po leksikografskom redosledu.
Prva linija standardnog ulaza sadrži broj \(k\) (\(1 \leq k \leq n\)), a naredna broj \(n\) (\(2 \leq n \leq 20\)).
Na standardni izlaz ispisati sve kombinacije. Svaka kombinacija treba da bude predstavljena nizom brojeva sortiranim strogo rastuće, a sve kombinacije treba da budu poređane u leksikografskom redosledu.
3 5
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
Zadatak rekurzivne funkcije biće da dopuni niz dužine \(k\) od pozicije \(i\) pa do kraja. Kada je \(i=k\), niz je popunjen i potrebno je obraditi (u našem slučaju ispisati) dobijenu kombinaciju. U suprotnom biramo element koji ćemo postaviti na poziciju \(i\). Pošto su kombinacije uređene strogo rastuće, on mora biti veći od prethodnog (ako prethodni ne postoji, onda može biti \(1\)) i manji ili jednak \(n\). Zapravo, ovo gornje ograničenje mora da se smanji. Pošto su elementi strogo rastući, a od pozicije \(i\) pa do kraja niza treba postaviti \(k-i\) elemenata, na poziciji \(i\) može biti \(n+i-k+1\) i tada će na poziciji \(k-1\) biti vrednost \(n\). U petlji stavljamo jedan po jedan od tih elemenata na poziciju \(i\) i rekurzivno nastavljamo generisanje od naredne pozicije. Dakle, u opštem slučaju, drvo rekurzivnih poziva neće biti binarno (funkcija može da napravi mnogo više od dva rekurzivna poziva).
// niz kombinacije dužine k na pozicijama [0, i) sadrži uređen
// niz elemenata iz skupa [1, n-i+1). Procedura na sve moguće
// načine dopunjava elementima iz skupa [1, n) tako da niz
// bude uređen rastući
void obradiSveKombinacije(vector<int>& kombinacija,
int i, int n) {
// tražena dužina kombinacije
int k = kombinacija.size();
// ako je popunjen ceo niz samo ispisujemo kombinaciju
if (i == k) {
obradi(kombinacija);
return;
}
// određujemo raspon elemenata na poziciji i
int pocetak = i == 0 ? 1 : kombinacija[i-1]+1;
int kraj = n + i - k + 1;
// jedan po jedan element upisujemo na poziciju i, pa
// nastavljamo generisanje rekurzivno
for (int x = pocetak; x <= kraj; x++) {
kombinacija[i] = x;
obradiSveKombinacije(kombinacija, i+1, n);
}
}
// nabraja i obradjuje sve kombinacije dužine k skupa
// {1, 2, ..., n}
void obradiSveKombinacije(int k, int n) {
vector<int> kombinacija(k);
obradiSveKombinacije(kombinacija, 0, n);
}#include <iostream>
#include <vector>
using namespace std;
// ispisuje kombinaciju na standarndi izlaz
void obradi(const vector<int>& kombinacija) {
for (int x : kombinacija)
cout << x << " ";
cout << endl;
}
// niz kombinacije dužine k na pozicijama [0, i) sadrži uređen
// niz elemenata iz skupa [1, n-i+1). Procedura na sve moguće
// načine dopunjava elementima iz skupa [1, n) tako da niz
// bude uređen rastući
void obradiSveKombinacije(vector<int>& kombinacija,
int i, int n) {
// tražena dužina kombinacije
int k = kombinacija.size();
// ako je popunjen ceo niz samo ispisujemo kombinaciju
if (i == k) {
obradi(kombinacija);
return;
}
// određujemo raspon elemenata na poziciji i
int pocetak = i == 0 ? 1 : kombinacija[i-1]+1;
int kraj = n + i - k + 1;
// jedan po jedan element upisujemo na poziciju i, pa
// nastavljamo generisanje rekurzivno
for (int x = pocetak; x <= kraj; x++) {
kombinacija[i] = x;
obradiSveKombinacije(kombinacija, i+1, n);
}
}
// nabraja i obradjuje sve kombinacije dužine k skupa
// {1, 2, ..., n}
void obradiSveKombinacije(int k, int n) {
vector<int> kombinacija(k);
obradiSveKombinacije(kombinacija, 0, n);
}
int main() {
int k, n;
cin >> k >> n;
obradiSveKombinacije(k, n);
return 0;
}Postoji način da izbegnemo rekurzivne pozive u petlji. Tokom rekurzije možemo da čuvamo informaciju o tome koji je raspon elemenata kojim se proširuje niz. Znamo da su to elementi skupa \(\{1, \ldots, n\}\), međutim, pošto su kombinacije sortirane rastuće skup kandidata je uži. U prethodnom programu smo najmanju vrednost za poziciju \(i\) određivali na osnovu vrednosti sa pozicije \(i-1\), međutim, alternativno možemo i eksplicitno da održavamo promenljive \(n_{min}\) i \(n_{max}\) koje određuju skup \(\{n_{min}, \ldots, n_{max}\}\) čiji se elementi raspoređuju u kombinaciji na pozicijama iz intervala \([i, k)\). Ako je taj interval prazan, kombinacija je popunjena i može se obraditi. U suprotnom, ako je \(n_{min} > n_{max}\), tada ne postoji vrednost koju je moguće staviti na poziciju \(i\), pa možemo izaći iz rekurzije, jer se trenutna kombinacija ne može popuniti do kraja. U suprotnom možemo razmotriti dve mogućnosti. Prvo na poziciju \(i\) možemo postaviti element \(n_{min}\) i rekurzivno izvršiti popunjavanje niza od pozicije \(i+1\), a drugo možemo taj element preskočiti i u rekurzivnom pozivu ponovo zahtevati da se popuni pozicija \(i\). U oba slučaja se skup elemenata sužava na \(\{n_{min}+1, \ldots, n_{max}\}\).
Pretragu možemo saseći i malo ranije. Naime, pošto su ponavljanja zabranjena kada je broj elemenata tog skupa (a to je \(n - n_{min} + 1\)) manji od broja preostalih pozicija koje treba popuniti (a to je \(k - i\)), već tada možemo saseći pretragu, jer ne postoji mogućnost da se kombinacija uspešno dopuni do kraja.
void obradiSveKombinacije(vector<int>& kombinacija, int i,
int n_min, int n_max) {
// tražena dužina kombinacije
int k = kombinacija.size();
// ako je popunjen ceo niz samo ispisujemo kombinaciju
if (i == k) {
obradi(kombinacija);
return;
}
// ako tekuću kombinaciju nije moguće popuniti do kraja
// prekidamo ovaj pokušaj
if (n_max - n_min + 1 < k - i)
return;
// vrednost n_min uključujemo na poziciju i, pa rekurzivno
// proširujemo tako dobijenu kombinaciju
kombinacija[i] = n_min;
obradiSveKombinacije(kombinacija, i+1, n_min+1, n_max);
// vrednost n_min preskačemo i isključujemo iz kombinacije
obradiSveKombinacije(kombinacija, i, n_min+1, n_max);
}
// nabraja i obradjuje sve kombinacije dužine k skupa
// {1, 2, ..., n}
void obradiSveKombinacije(int k, int n) {
vector<int> kombinacija(k);
obradiSveKombinacije(kombinacija, 0, 1, n);
}#include <iostream>
#include <vector>
using namespace std;
// ispisuje kombinaciju na standarndi izlaz
void obradi(const vector<int>& kombinacija) {
for (int x : kombinacija)
cout << x << " ";
cout << endl;
}
void obradiSveKombinacije(vector<int>& kombinacija, int i,
int n_min, int n_max) {
// tražena dužina kombinacije
int k = kombinacija.size();
// ako je popunjen ceo niz samo ispisujemo kombinaciju
if (i == k) {
obradi(kombinacija);
return;
}
// ako tekuću kombinaciju nije moguće popuniti do kraja
// prekidamo ovaj pokušaj
if (n_max - n_min + 1 < k - i)
return;
// vrednost n_min uključujemo na poziciju i, pa rekurzivno
// proširujemo tako dobijenu kombinaciju
kombinacija[i] = n_min;
obradiSveKombinacije(kombinacija, i+1, n_min+1, n_max);
// vrednost n_min preskačemo i isključujemo iz kombinacije
obradiSveKombinacije(kombinacija, i, n_min+1, n_max);
}
// nabraja i obradjuje sve kombinacije dužine k skupa
// {1, 2, ..., n}
void obradiSveKombinacije(int k, int n) {
vector<int> kombinacija(k);
obradiSveKombinacije(kombinacija, 0, 1, n);
}
int main() {
int k, n;
cin >> k >> n;
obradiSveKombinacije(k, n);
return 0;
}Jedan način da se zadatak reši bez rekurzije je da se upotrebi funkcija za određivanje naredne kombinacije u leksikografskom poretku koja je opisana u zadatku [Sledeća kombinacija].
// nabraja i obradjuje sve kombinacije dužine k skupa
// {1, 2, ..., n}
void obradiSveKombinacije(int k, int n) {
// krecemo od kombinacije 1, 2, ..., k
vector<int> kombinacija(k);
for (int i = 0; i < k; i++)
kombinacija[i] = i + 1;
// obradjujemo kombinacije dokle god postoji sledeca
do {
obradi(kombinacija);
} while (sledecaKombinacija(n, kombinacija));
}#include <iostream>
#include <vector>
using namespace std;
// ispisuje kombinaciju na standarndi izlaz
void obradi(const vector<int>& kombinacija) {
for (int x : kombinacija)
cout << x << " ";
cout << endl;
}
// pronalazi sledecu kombinaciju u leksikografskom redosledu
bool sledecaKombinacija(int n, vector<int>& kombinacija) {
// tražena dužina kombinacije
int k = kombinacija.size();
// krećemo od kraja i tražimo prvu poziciju koja nije na maksimumu
// tj. koja se može povećati. Maksimumi od kraja su n, n-1, n-2, ...
int i;
for (i = k-1; i >= 0 && kombinacija[i] == n; i--, n--)
;
// ako takva pozicija ne postoji, tekuća kombinacija je maksimalna
if (i < 0)
return false;
// uvećavamo poslednji element koji se može povećati
kombinacija[i]++;
// iza njega slažemo redom brojeve za jedan veće
for (i++; i < k; i++)
kombinacija[i] = kombinacija[i-1] + 1;
return true;
}
// nabraja i obradjuje sve kombinacije dužine k skupa
// {1, 2, ..., n}
void obradiSveKombinacije(int k, int n) {
// krecemo od kombinacije 1, 2, ..., k
vector<int> kombinacija(k);
for (int i = 0; i < k; i++)
kombinacija[i] = i + 1;
// obradjujemo kombinacije dokle god postoji sledeca
do {
obradi(kombinacija);
} while (sledecaKombinacija(n, kombinacija));
}
int main() {
int k, n;
cin >> k >> n;
obradiSveKombinacije(k, n);
return 0;
}Sve permutacije brojeva od \(1\) do \(n\) se mogu poređati leksikografski. Na primer za \(n=3\) permutacije u leksikografskom poretku su
123 132 213 231 312 321
Napisati program kojim se za dati prirodan broj \(n\) i datu permutaciju brojeva od \(1\) do \(n\) prikazuje sledeća permutacija u leksikografskom poretku (prva permutacija koja se nalazi posle date permutacije).
Prva linija standardnog ulaza sadrži prirodan broj \(n\) (\(n < 1000\)). U svakoj od \(n\) narednih linija standardnog ulaza, nalaze se redom elementi permutacije, svaki u posebnoj liniji.
Na standardnom izlazu prikazati redom elemente sledeće permutacije u leksikografskom poretku, svaki element u posebnoj liniji. Ako ne postoji sledeća permutacija (data permutacija je poslednja) prikazati u jednoj liniji poruku ne postoji.
5 3 1 4 5 2
3 1 5 2 4
3 3 2 1
ne postoji
Primer 6.1. Razmotrimo permutaciju \(13542\). Zamenom elementa \(2\) i \(4\) bi se dobila permutacija \(13524\) koja je leksikografski manja od polazne i to nam ne odgovara. Slično bi se desilo i da se zamene elementi \(5\) i \(4\). Činjenica da je niz \(542\) strogo opadajući nam govori da nije mogući ni na koji način razmeniti ta tri elementa da se dobije leksikografski veća permutacija, tj. da je ovo najveća permutacija koja počinje sa \(13\). Dakle, naredna permutacija će biti leksikografski najmanja permutacija koja počinje sa \(14\), a to je \(14235\).
Dakle, u prvom koraku algoritma pronalazimo prelomnu tačku, tj. prvu poziciju \(i\) zdesna, takvu da je \(a_i < a_{i+1}\) (za sve \(i+1 \leq k < n-1\) važi da je \(a_k > a_{k+1}\)). Ovo radimo najjobičnijom linearnom pretragom. Ako takva pozicija ne postoji, naša permutacija je skroz opadajuća i samim tim leksikografski najveća. Nakon toga, pronalazimo prvu poziciju \(j\) zdesna takvu da je \(a_i < a_j\) (opet linearnom pretragom) i razmenjujemo elemente na pozicijama \(i\) i \(j\). Pošto je ovom razmenom rep iza pozicije \(i\) i dalje striktno opadajući, da bismo dobili željenu permutaciju (leksikografski najmanju permutaciju koja počinje sa \(a_0\ldots a_{i-1}a_j\)), potrebno je obrnuti redosled elemenata repa tj. deo niza od pozicije \(i+1\) do kraja niza.
Primer 6.2. Ako označimo pozicije elemenata dobijamo \(1^03^15^24^32^4\). Zato je \(i=1\) i \(a_i = 3\), dok je \(j=3\) i \(a_j = 4\). Nakon razmene dobijamo \(1^04^15^23^32^4\). Da bismo dobili traženu permutaciju \(1^04^12^23^35^4\) obrćemo deo niza od pozicije \(i+1 = 2\) do kraja niza.
bool sledecaPermutacija(vector<int>& a){
int n = a.size();
// linearnom pretragom pronalazimo prvu poziciju i takvu da
// je a[i] > a[i+1]
int i = n - 2;
while (i >= 0 && a[i] > a[i+1])
i--;
// ako takve pozicije nema,
// permutacija a je leksikografski maksimalna
if (i < 0) return false;
// linearnom pretragom pronalazimo prvu poziciju j takvu da
// je a[j] > a[i]
int j = n - 1;
while (a[j] < a[i])
j--;
// razmenjujemo elemente na pozicijama i i j
swap(a[i], a[j]);
// obrcemo deo niza od pozicije i+1 do kraja
for (j = n - 1, i++; i < j; i++, j--)
swap(a[i], a[j]);
return true;
}#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool sledecaPermutacija(vector<int>& a){
int n = a.size();
// linearnom pretragom pronalazimo prvu poziciju i takvu da
// je a[i] > a[i+1]
int i = n - 2;
while (i >= 0 && a[i] > a[i+1])
i--;
// ako takve pozicije nema,
// permutacija a je leksikografski maksimalna
if (i < 0) return false;
// linearnom pretragom pronalazimo prvu poziciju j takvu da
// je a[j] > a[i]
int j = n - 1;
while (a[j] < a[i])
j--;
// razmenjujemo elemente na pozicijama i i j
swap(a[i], a[j]);
// obrcemo deo niza od pozicije i+1 do kraja
for (j = n - 1, i++; i < j; i++, j--)
swap(a[i], a[j]);
return true;
}
// ispisujemo elemente vektora
void prikazi(const vector<int>& a) {
for (int x: a)
cout << x << endl;
}
int main() {
// ucitavamo polaznu permutaciju
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
// odredjujemo sledecu i ispisujemo rezultat
if (sledecaPermutacija(a))
prikazi(a);
else
cout << "ne postoji" << endl;
return 0;
}U jeziku C++ postoji bibliotečka funkcija next_permutation koja određuje sledeću permutaciju u leksikografskom redosledu (i vraća informaciju o tome da li ona postoji).
// ucitavamo polaznu permutaciju
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
// odredjujemo sledecu i ispisujemo rezultat
if (next_permutation(begin(a), end(a)))
obradi(a);
else
cout << "ne postoji" << endl;#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// ispisujemo elemente vektora
void obradi(const vector<int>& a) {
for (int x: a)
cout << x << endl;
}
int main() {
// ucitavamo polaznu permutaciju
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
// odredjujemo sledecu i ispisujemo rezultat
if (next_permutation(begin(a), end(a)))
obradi(a);
else
cout << "ne postoji" << endl;
return 0;
}