Проблеми се често могу решити исцрпном претрагом (грубом силом), што подразумева да се испитају сви могући кандидати за решења. Предуслов за то је да умемо све те кандидате да набројимо. Иако у реалним применама простор потенцијалних решења може имати различиту структуру, показује се да је у великом броју случаја то простор одређених класичних комбинаторних објеката: свих подскупова неког коначног скупа, свих варијација (са или без понављања), свих комбинација (са или без понављања), свих пермутација, свих партиција и слично. У овом поглављу ћемо проучити механизме њиховог систематичног генерисања. Нагласимо да по правилу оваквих објеката има експоненцијално много у односу на величину улаза, тако да су сви алгоритми практично неупотребљиви осим за веома мале димензије улаза.
Објекти се обично представљају \(n\)-торкама бројева, при чему се исти објекти могу торкама моделовати на различите начине. На пример, сваки подскуп скупа \(\{a_0, \ldots, a_{n-1}\}\) се може представити коначним низом индекса елемената који му припадају. Да би сваки подскуп био јединствено представљен, потребно је да тај низ буде канонизован (на пример, уређен строго растући). На пример, торка \((0, 2, 3)\) једнозначно одређује подскуп \(\{a_0, a_2, a_3\}\). Други начин да се подскупови представе су \(n\)-торке логичких вредности или вредности 0-1. На пример, ако је \(n=6\), и ако претпоставимо да се битови читају слева надесно, тада торка \(101100\) означава скуп \(\{a_0, a_2, a_3\}\).
Сви објекти се обично могу представити дрветом и то дрво одговара процесу њиховог генерисања тј. обиласка (оно се не прави експлицитно, у меморији, али нам помаже да разумемо и организујемо поступак претраге). Обилазак дрвета се најједноставније изводи у дубину (често рекурзивно). За прву наведену репрезентацију подскупова дрво је дато на слици 10. Сваки чвор дрвета одговара једном подскупу, при чему се одговарајућа торка очитава на гранама пута који води од корена до тог чвора.
За другу наведену репрезентацију подскупова дрво је дато на слици 11. На почетку се бира да ли ће елемент \(a_0\) бити укључен у подскуп, на наредном нивоу да ли ће бити укључен елемент \(a_1\), затим елемент \(a_2\) и тако даље. Само листови дрвета у којима је за сваки елемент донета одлука да ли припада или не припада подскупу, одговарају подскуповима, при чему се одговарајућа торка логичких вредности очитава на гранама пута који води од корена до тог чвора.
Приметимо да оба дрвета садрже \(2^n\) чворова којима се представљају подскупови (у првом случају су то сви чворови дрвета, а у другом само листови).
Приликом генерисања објеката често је пожељно ређати их одређеним редом. С обзиром на то то да се сви комбинаторни објекти представљају одређеним торкама (коначним низовима), природан поредак међу њима је лексикографски поредак (који се користи за утврђивање редоследа речи у речнику). Подсетимо се, торка \(a_0\ldots a_{m-1}\) лексикографски претходи торци \(b_0\ldots b_{n-1}\) акко постоји неки индекс \(i\) такав да за свако \(0 \leq j < i\) важи \(a_j = b_j\) и важи или да је \(a_i < b_i\) или да је \(i = m < n\). На пример важи да је \(11 < 112 < 221\) (овде је \(i=2\), а затим \(i=0\)).
На пример, ако подскупове скупа \(\{1, 2, 3\}\) представимо на први начин, торкама у којима су елементи уређени растуће, лексикографски поредак би био \(\emptyset\), \(\{1\}\), \(\{1, 2\}\), \(\{1, 2, 3\}\), \(\{1, 3\}\), \(\{2\}\), \(\{2, 3\}\), \(\{3\}\). Ако бисмо их представљали на други начин, торкама у којима се нулама и јединицама одређује да ли је неки елемент укључен у подскуп, лексикографски редослед би био: 000 (\(\emptyset\)), 001 (\(\{3\}\)), 010(\(\{2\}\)), 011(\(\{2, 3\}\)), 100(\(\{1\}\)), 101(\(\{1,3\}\)), 110(\(\{1,2\}\)) и 111(\(\{1,2,3\}\)).
У наставку ће бити приказано како је могуће набројати све објекте који имају неку задату комбинаторну структуру. У већини задатака могуће је разматрати две врсте решења. Једна група решења је заснована на рекурзивном поступку набрајања објеката, док је друга група решења заснована на проналажењу наредног комбинаторног објекта у односу на неки задати редослед (најчешће лексикорафски).
Написати програм који одређује подскуп скупа бројева \(\{1, \ldots, n\}\) који у лексикографском редоследу следи непосредно иза датог подскупа. Подскупови су задати у облику строго растуће сортираних низова.
Прва линија садржи број \(n\) (\(1 \leq n \leq 100\)), а наредна линија садржи подскуп чији су елементи задати сортирано растуће, раздвојени по једним размаком.
На стандардни излаз у једној линији исписати елементе траженог подскупа тј. - ако је учитани подскуп лексикографски највећи.
5 1 2 3 4 5
1 2 3 5
5 5
-
Напишимо, на пример, лексикографски уређен списак свих подскупова скупа бројева од 1 до 4.
-, 1, 12, 123, 1234, 124, 13, 134, 14, 2, 23, 234, 24, 3, 34, 4
Можемо приметити да постоје два начина да се дође до наредног подскупа. Анализирајмо ове скупове у истом редоследу, груписане у колоне на основу броја елемената.
- 1 12 123 1234 124 13 134 14 2 23 234 24 3 34 4
Један начин је проширивање када се наредни подскуп добија додавањем неког елемента у претходни. То су кораци у претходној табели код којих се прелази из једне у наредну колону. Да би добијени подскуп следио непосредно иза претходног у лексикографском редоследу, додати елемент подскупу мора бити најмањи могући. Пошто је сваки подскуп сортиран, елемент мора бити за један већи од последњег елемента подскупа који се проширује (изузетак је празан скуп, који се проширује елементом 1). Једини случај када проширивање није могуће је када је последњи елемент подскупа највећи могући (у нашем примеру то је 4).
Други начин је скраћивање када се наредни елемент добија уклањањем неких елемената из подскупа и изменом преосталих елемената. То су кораци у претходној табели код којих се прелази са краја једне у наредну врсту. У овом случају скраћивање функционише тако што се из подскупа избаци завршни највећи елемент, а затим се највећи од преосталих елемената увећа за 1 (он не може бити највећи, јер су елементи унутар сваког подскупа строго растући). Ако након избацивања највећег елемента остане празан скуп, наредна комбинација не постоји.
Подскупове можемо представити динамичким низом који нам омогућва да елементе додајемо и уклаљамо са десног краја. У језику C++ можемо употребити вектор (тј. колекцију 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;
}Подскупове можемо чувати и у оквиру низа који је унапред алоциран тако да може да смести елементе највећег подскупа (оног који има тачно \(n\) елемената). У том случају је неопходно да одржавамо и променљиву у којој бележимо број елемената подскупа. Пошто се она мења у функцији која одређује наредни подскуп, потребно је пренети је по референци.
// 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;
}Написати програм који исписује све подскупове датог скупа.
Са стандардног улаза се учитава број \(n\) (важи \(3 \leq n \leq 10\)), а затим \(n\) природних бројева, растуће сортираних, раздвојених по једним размаком.
На стандардни излаз исписати све подскупове учитаног скупа бројева, сваки у посебном реду, са елементима раздвојеним једним размаком. Прво се ређају подскупови у којима први елемент није укључен, а затим они у којима јесте. У свакој од те две групе, прво се исписују подскупови у којима други елемент није укључен, а затим они где јесте и тако даље.
3 1 2 3
3 2 2 3 1 1 3 1 2 1 2 3
Генерисање свих подскупова одговара генерисању свих варијација дужине \(n\) од нула и јединица (сваки елемент је или укључен или искључен). Поредак описан у поставци задатка указује на то да подскупови треба да буду уређени лексикографски, у односу на њихову репрезентацију у облику варијација.
Опишимо индуктивно-рекурзивну конструкцију функције која генерише све подскупове скупа \(S\).
Ако је скуп \(S\) празан, онда је једини његов подскуп празан.
Ако скуп \(S\) није празан, онда се може разложити на неки елемент \(x\) и скуп \(S' = S \setminus x\) добијен када се тај елемент избаци из полазног скупа. Пошто је скуп \(S'\) мањи од скупа \(S\), његови се подскупови могу одредити рекурзивно. Сви подскупови полазног скупа \(S\) су онда они који су одређени за мањи скуп \(S'\), као и сви они који се од њих добијају додавањем издвојеног елемента \(x\).
Претходну конструкцију није економично програмски реализовати, јер се претпоставља да резултат рада функције представља скуп свих подскупова скупа. Уместо такве функције дефинисаћемо процедуру која неће истовремено чувати и враћати све подскупове већ само један по један набројати и обрадити (у нашем случају само исписати).
До решења се може доћи тако што се у рекурзивној функцији прослеђује неки подсуп \(P\) скупа \(\{a_0, \ldots, a_{i-1}\}\) и који она на све могуће начине проширује елементима скупа \(\{a_i, \ldots, a_{n-1}\}\).
Ако је скуп \(\{a_i, \ldots, a_{n-1}\}\) празан (ако је \(i=n\)) тада је подскуп \(P\) комплетно формиран и обрађује се (тј. исписује).
У супротном разматрамо елемент \(a_i\) и две могућности: да тај елемент буде изостављен из подсупа и могућност да тај елемент буде додат у подскуп \(P\). У оба случаја настављамо рекурзивно проширивање скупа \(P\) (прво непроширеног, а затим и проширеног елементом \(a_i\)) елементима скупа \(\{a_{i+1}, \ldots, a_{n-1}\}\).
Иницијално је \(i=0\), а подскуп је празан (празан скуп је, заиста, једини подскуп празног супа \(\{a_0, \ldots, a_{i-1}\}\) и он се на све могуће начине проширује елементима скупа \(\{a_i, \ldots, a_{n-1}\} = \{a_0, \ldots, a_{n-1}\}\)).
Иако многи савремени језици пружају тип за репрезентовање скупова, имплементација је једноставнија и ефикаснија ако се елементи скупа чувају у низу. Да бисмо избегли потребу за продужавањем и скраћивањем низа и коришћењем динамичких низова, листа или вектра, низ можемо алоцирати на максималну могућу дужину (број елемената полазног скупа) и паралелно са низом можемо одржавати број елемената подскупа који је тренутно смештен у низ (он је скоро увек строго мањи од дужине низа).
Дакле, дефинишемо рекурзивну функцију која на сваком наредном нивоу рекурзије обрађује наредни елемент полазног скупа (представљеног низом), све док се не исцрпе сви елементи. У првом случају тај елемент не додаје у резултујући подскуп (такође представљен низом, који прослеђујемо као додатни параметар) и прелази на наредни ниво рекурзије, а у другом га додаје на крај тренутног резултујућег подскупа и прелази на наредни ниво рекурзије. Када се цео полазни низ исцрпи (када је дубина рекурзије једнака дужини полазног низа), тада се тренутно акумулирани подскуп обрађује тј. исписује.
Рад рекурзивне функције одговара слици 11.
// 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;
}У имплементацији можемо користити и библиотечке колекције за репрезентовање низа елемената. Међутим, треба бити веома обазрив јер је могуће да се током рекурзије граде нови низови и копирају елементи, што знатно утиче на ефикасност. Наредна имплементација је због тога веома лоша.
// 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;
}Могуће је направити решење које користи библиотечке колекција података, а уједно не врши њихово копирање и довољно је ефикасно. У имплементацији се користе два низа (један за скуп, други за подскуп) који се током рада алгоритма мењају. Низови ће се мењати додавањем и укљањањем елемената са краја. Зато је пре почетка функције неохподно обрнути редослед елемената у низу (да би се на крају прво нашли почетни елементи низа).
У имплементацијама које мењају низове често је важно осигурати да се на крају тела рекурзивне функције стање низова врати на исто стање какво је било на уласку у функцију, јер се тиме гарантује да рекурзивни позив неће модификовати низове који су му предати као параметри (што користимо када се ослањамо на то да ће и након првог и након другог рекурзивног позива скуп и подскуп бити исти какви су били и пре тог рекурзивног позива).
// 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;
}Једно решење је да се у посебном низу логичких вредности набрајају све варијације скупа тачно-нетачно. Свака таква варијација одговара једном подскупу, тако што се у подскуп укључују елементи са оних позиција на којима је је вредност тачно. Варијације набрајамо коришћењем функције за одређивање следеће варијације.
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;
}Написати програм који одређује наредну варијацију дужине \(k\) скупа \(\{1, \ldots, n\}\) у лексикографском поретку.
Прва линија стандардног улаза садржи број \(k\) (\(1 \leq k \leq 100\)), а друга број \(n\) (\(1 \leq n \leq 100\)). У трећој линији се налази варијација описана бројевима раздвојеним по једним размаком.
На стандардни излаз исписати следећу варијацију у лексикографском поретку, ако она постоји, или -, ако је учитана варијација лексикографски максимална.
5 4 1 1 2 3 4
1 1 2 4 1
Следећа варијација у лексикографском поретку се може генерисати тако што се увећа последњи број у варијацији који се може увећати, и што се након увећавања сви бројеви иза увећаног броја поставе на \(1\). Позиција на којој се број увећава назива се преломна тачка (енгл. turning point). На пример, ако набрајамо варијације скупа \(\{1, 2, 3\}\) дужине \(5\) наредна варијација за варијацију \(21332\) је \(21333\) (преломна тачка је позиција \(4\), која је последња позиција у низу), док је њој наредна варијација \(22111\) (преломна тачка је позиција \(1\) на којој се налазио елемент \(1\)). Низ \(33333\) нема преломну тачку, па самим тим ни лексикографски следећу варијацију.
Један начин имплементације је да преломну тачку нађемо линеарном претрагом од краја низа, ако преломна тачка постоји да увећамо елемент и да од следеће позиције до краја низ попунимо јединицама. Међутим, те две фазе можемо објединити. Варијацију обилазимо од краја постављајући на 1 сваки елемент у варијацији који је једнак броју \(n\). Ако се зауставимо пре него што смо стигли до краја низа, значи да смо пронашли елемент који се може увећати и увећавамо га. У супротном је варијација имала све елементе једнаке \(n\) и била је максимална у лексикографском редоследу.
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;
}Напиши програм који одређује све варијације са понављањем дужине \(k\) скупа \(\{1, \ldots, n\}\).
Са стандардног улаза се учитава број \(n\) (\(1 \leq n \leq 5\)) и у наредној линији број \(k\) (\(1 \leq k \leq 5\)).
На стандардни излаз исписати све варијације, сортиране лексикографски.
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
Варијације се могу набројати индуктивно рекурзивном конструкцијом.
Једина варијација дужине нула је празна.
Све варијације дужине \(k\) се могу добити тако што се на прво место упише било који од бројева од \(1\) до \(n\), а затим се преостала места допуне свим варијацијама дужине \(k-1\).
Рецимо и да је могуће на последње место постављати један по један број од \(1\) до \(n\), а затим рекурзивно попуњавати префикс, но тиме би редослед варијација био другачији од траженог.
Уместо да дефинишемо функцију која враћа колекцију варијација, дефинисаћемо рекурзивну процедуру која прима низ коме су попуњени сви елементи осим последњих \(k\), и који ће на све могуће начине допуњавати варијацијама дужине \(k\) (која ће се смањивати кроз рекурзивне позиве). Дакле, након попуњеног дела низа постављамо једну по једну вредност од \(1\) до \(n\) и затим рекурзивно позивамо процедуру да попуни остатак низа (тиме што смањујемо дужину \(k\) и тиме прелазимо на наредну позицију).
Да бисмо избегли потребу за динамичким проширивањем низова унапред ћемо алоцирати низ дужине \(k\), а онда ћемо му у рекурзији попуњавати једну по једну позицију (текућа позиција се може одредити као разлика између дужине низа и текуће вредности броја \(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;
}Друга могућност је да се крене од лексикографски најмање варијације (то је варијација \(\underbrace{11\ldots 11}_{k}\)) и да се коришћењем функције описане у задатку [Следећа варијација] одређује наредна варијација дате варијације у односу на лексикографски редослед, све док таква постоји.
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;
}Комбинације дужине \(k\) од \(n\) елемената подразумевају да се врши одабир \(k\) елемената скупа \(\{1, \ldots, n\}\), слично као што се, на пример, у игри лото бира 7 од 39 куглица. Напиши програм који за дате вредности \(k\) и \(n\) набраја и исписује све комбинације, поређане по лексикографском редоследу.
Прва линија стандардног улаза садржи број \(k\) (\(1 \leq k \leq n\)), а наредна број \(n\) (\(2 \leq n \leq 20\)).
На стандардни излаз исписати све комбинације. Свака комбинација треба да буде представљена низом бројева сортираним строго растуће, а све комбинације треба да буду поређане у лексикографском редоследу.
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
Задатак рекурзивне функције биће да допуни низ дужине \(k\) од позиције \(i\) па до краја. Када је \(i=k\), низ је попуњен и потребно је обрадити (у нашем случају исписати) добијену комбинацију. У супротном бирамо елемент који ћемо поставити на позицију \(i\). Пошто су комбинације уређене строго растуће, он мора бити већи од претходног (ако претходни не постоји, онда може бити \(1\)) и мањи или једнак \(n\). Заправо, ово горње ограничење мора да се смањи. Пошто су елементи строго растући, а од позиције \(i\) па до краја низа треба поставити \(k-i\) елемената, на позицији \(i\) може бити \(n+i-k+1\) и тада ће на позицији \(k-1\) бити вредност \(n\). У петљи стављамо један по један од тих елемената на позицију \(i\) и рекурзивно настављамо генерисање од наредне позиције. Дакле, у општем случају, дрво рекурзивних позива неће бити бинарно (функција може да направи много више од два рекурзивна позива).
// 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;
}Постоји начин да избегнемо рекурзивне позиве у петљи. Током рекурзије можемо да чувамо информацију о томе који је распон елемената којим се проширује низ. Знамо да су то елементи скупа \(\{1, \ldots, n\}\), међутим, пошто су комбинације сортиране растуће скуп кандидата је ужи. У претходном програму смо најмању вредност за позицију \(i\) одређивали на основу вредности са позиције \(i-1\), међутим, алтернативно можемо и експлицитно да одржавамо променљиве \(n_{min}\) и \(n_{max}\) које одређују скуп \(\{n_{min}, \ldots, n_{max}\}\) чији се елементи распоређују у комбинацији на позицијама из интервала \([i, k)\). Ако је тај интервал празан, комбинација је попуњена и може се обрадити. У супротном, ако је \(n_{min} > n_{max}\), тада не постоји вредност коју је могуће ставити на позицију \(i\), па можемо изаћи из рекурзије, јер се тренутна комбинација не може попунити до краја. У супротном можемо размотрити две могућности. Прво на позицију \(i\) можемо поставити елемент \(n_{min}\) и рекурзивно извршити попуњавање низа од позиције \(i+1\), а друго можемо тај елемент прескочити и у рекурзивном позиву поново захтевати да се попуни позиција \(i\). У оба случаја се скуп елемената сужава на \(\{n_{min}+1, \ldots, n_{max}\}\).
Претрагу можемо сасећи и мало раније. Наиме, пошто су понављања забрањена када је број елемената тог скупа (а то је \(n - n_{min} + 1\)) мањи од броја преосталих позиција које треба попунити (а то је \(k - i\)), већ тада можемо сасећи претрагу, јер не постоји могућност да се комбинација успешно допуни до краја.
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;
}Један начин да се задатак реши без рекурзије је да се употреби функција за одређивање наредне комбинације у лексикографском поретку која је описана у задатку [Следећа комбинација].
// 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;
}Све пермутације бројева од \(1\) до \(n\) се могу поређати лексикографски. На пример за \(n=3\) пермутације у лексикографском поретку су
123 132 213 231 312 321
Написати програм којим се за дати природан број \(n\) и дату пермутацију бројева од \(1\) до \(n\) приказује следећа пермутација у лексикографском поретку (прва пермутација која се налази после дате пермутације).
Прва линија стандардног улаза садржи природан број \(n\) (\(n < 1000\)). У свакој од \(n\) наредних линија стандардног улаза, налазе се редом елементи пермутације, сваки у посебној линији.
На стандардном излазу приказати редом елементе следеће пермутације у лексикографском поретку, сваки елемент у посебној линији. Ако не постоји следећа пермутација (дата пермутација је последња) приказати у једној линији поруку ne postoji.
5 3 1 4 5 2
3 1 5 2 4
3 3 2 1
ne postoji
Пример 6.1. Размотримо пермутацију \(13542\). Заменом елемента \(2\) и \(4\) би се добила пермутација \(13524\) која је лексикографски мања од полазне и то нам не одговара. Слично би се десило и да се замене елементи \(5\) и \(4\). Чињеница да је низ \(542\) строго опадајући нам говори да није могући ни на који начин разменити та три елемента да се добије лексикографски већа пермутација, тј. да је ово највећа пермутација која почиње са \(13\). Дакле, наредна пермутација ће бити лексикографски најмања пермутација која почиње са \(14\), а то је \(14235\).
Дакле, у првом кораку алгоритма проналазимо преломну тачку, тј. прву позицију \(i\) здесна, такву да је \(a_i < a_{i+1}\) (за све \(i+1 \leq k < n-1\) важи да је \(a_k > a_{k+1}\)). Ово радимо најјобичнијом линеарном претрагом. Ако таква позиција не постоји, наша пермутација је скроз опадајућа и самим тим лексикографски највећа. Након тога, проналазимо прву позицију \(j\) здесна такву да је \(a_i < a_j\) (опет линеарном претрагом) и размењујемо елементе на позицијама \(i\) и \(j\). Пошто је овом разменом реп иза позиције \(i\) и даље стриктно опадајући, да бисмо добили жељену пермутацију (лексикографски најмању пермутацију која почиње са \(a_0\ldots a_{i-1}a_j\)), потребно је обрнути редослед елемената репа тј. део низа од позиције \(i+1\) до краја низа.
Пример 6.2. Ако означимо позиције елемената добијамо \(1^03^15^24^32^4\). Зато је \(i=1\) и \(a_i = 3\), док је \(j=3\) и \(a_j = 4\). Након размене добијамо \(1^04^15^23^32^4\). Да бисмо добили тражену пермутацију \(1^04^12^23^35^4\) обрћемо део низа од позиције \(i+1 = 2\) до краја низа.
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;
}У језику C++ постоји библиотечка функција next_permutation која одређује следећу пермутацију у лексикографском редоследу (и враћа информацију о томе да ли она постоји).
// 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;
}