Stringom \(s\) dat je skup malih slova engleskog alfabeta (slova su u stringu uređena u rastućem poretku) i prirodan broj \(k\). Napisati program kojim se prikazuju u leksikografskom poretku sve reči dužine \(k\) koje se mogu formirati od datog skupa.
Na standardnom ulazu u prvoj liniji nalazi se string \(s\) dužine najviše 10, u drugoj liniji nalazi se prirodan broj \(k\) (\(k \leq 6\), \(k \leq n\)).
Na standardnom izlazu prikazati tražene reči u leksikografskom poretku, svaku reč u posebnoj liniji.
amx 2
aa am ax ma mm mx xa xm xx
Zadatak možemo rešiti veoma slično zadatku [Sve varijacije]. Definišemo rekurzivnu funkciju koja prima skup slova, reč koja se malo po malo popunjava i indeks naredne pozicije \(i\) u toj reči koju treba popuniti (inicijalno je ta pozicija jednaka nuli). Kada je pozicija jednaka dužini reči, reč je cela formirana i može se ispisati. U suprotnom na poziciju \(i\) postavljamo redom jedno po jedno slovo iz datog skupa i rekurzivno pozivamo funkciju da se popune slova od pozicije \(i+1\), nadalje.
void sveReci(string& s, const string& slova, int i) {
if (i == s.length())
cout << s << endl;
else
for (char slovo : slova) {
s[i] = slovo;
sveReci(s, slova, i+1);
}
}
void sveReci(const string& slova, int k) {
string s;
s.resize(k);
sveReci(s, slova, 0);
}#include <iostream>
#include <string>
#include <vector>
using namespace std;
void sveReci(string& s, const string& slova, int i) {
if (i == s.length())
cout << s << endl;
else
for (char slovo : slova) {
s[i] = slovo;
sveReci(s, slova, i+1);
}
}
void sveReci(const string& slova, int k) {
string s;
s.resize(k);
sveReci(s, slova, 0);
}
int main() {
ios_base::sync_with_stdio(false);
string slova;
int k;
cin >> slova;
cin >> k;
sveReci(slova, k);
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. Napisati program koji za datu kombinaciju određuje narednu u leksikografskom poretku.
Sa standardnog ulaza se unosi broj \(n\) (\(2 \leq n \leq 100\)) a zatim u narednom redu jedna kombinacija dužine \(1 \leq k \leq n\). Elementi su zadati sortirani rastuće, odvojeni po jednim razmakom.
Na standardni izlaz ispisati kombinaciju koja je naredna u leksikografskom redosledu u odnosu na datu, tj. - ako takva kombinacija ne postoji.
5 1 3 4
1 3 5
5 1 3 5
1 4 5
5 3 4 5
-
Opišimo postupak kojim od date kombinacije možemo dobiti sledeću kombinaciju u leksikografskom redosledu.
Napišimo, ilustracije radi, sve kombinacije dužine 3 iz skupa od 5 elemenata.
Ponovo tražimo prelomnu tačku tj. element koji se može uvećati. Pošto su kombinacije dužine \(k\) i organizovane su strogo rastuće, maksimalna vrednost na poslednjoj poziciji je \(n\), na pretposlednjoj \(n-1\) itd. Dakle, poslednji element se može uvećati ako nije jednak \(n\), pretposlednji ako nije jednak \(n-1\) itd. Prelomna tačka je pozicija prvog elementa koji je manji od svog maksimuma. Ako pozicije brojimo od \(0\), maksimum na poziciji \(k-1\) je \(n\), na poziciji \(k-2\) je \(n-1\) itd. tako da je maksimum na poziciji \(i\) jednak \(n-k+1+i\). Ako prelomna tačka ne postoji (ako su sve vrednosti na svojim maksimumima), naredna kombinacija u leksikografskom redosledu ne postoji. U suprotnom uvećavamo element na prelomnoj poziciji i da bismo nakon toga dobili leksikografski što manju kombinaciju, sve elemente iza njega postavljamo na najmanje moguće vrednosti. Pošto kombinacija mora biti sortirana strogo rastuće, nakon uvećanja prelomne vrednosti sve elemente iza nje postavljamo na vrednost koja je za jedan veća od vrednosti njoj prethodne vrednosti u nizu.
Primer 6.A.1. Na primer, ako je \(n=6\) i \(k=4\), tada je naredna kombinacija kombinaciji \(1256\), kombinacija \(1345\) - prelomna vrednost je \(2\) i ona se može uvećati na \(3\), nakon čega slažemo redom elemente za po jedan veće.
Prikažimo sve prelomne tačke prilikom generisanja kombinacija dužine \(n=3\) iz skupa od \(k=5\) elemenata.
\[12{\bf 3} \rightarrow12{\bf 4} \rightarrow1{\bf 2}5 \rightarrow13{\bf 4} \rightarrow1{\bf 3}5 \rightarrow{\bf 1}45 \rightarrow23{\bf 4} \rightarrow2{\bf 3}5 \rightarrow{\bf 2}45 \rightarrow345\]
Napiši program koji generiše i ispisuje sve permutacije skupa \(\{1, 2, \ldots, n\}\).
Sa standardnog ulaza se učitava broj \(n\) (\(1 \leq n \leq 8\)).
Na standardni izlaz ispisati tražene permutacije. Svaku permutaciju ispisati u posebnom redu, a elemente razdvojiti po jednim razmakom. Redosled permutacija može biti proizvoljan.
3
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Permutacije se mogu rekurzivno generisati veoma slično postupku generisanja varijacija bez ponavljanja. U rekurzivnoj funkciji obrađujemo jednu po jednu poziciju i na nju stavljamo one elemente skupa \(\{1, \ldots, n\}\) koji se ne nalaze na prethodnim pozicijama. Da bi se izbegla linearna pretraga prethodnih pozicija, moguće je koristiti pomoćni niz logičkih vrednosti u kome se za svaki element označava da li je već iskorišćen ili nije.
// popunjava se permutacija a od pozicije i nadalje elementima
// skupa {1, ..., n} pri cemu se u nizu upotrebljen beleze
// upotrebljeni elementi u delu permutacije pre pozicije i
void permutacije(vector<int>& a, int n,
vector<bool>& upotrebljen, int i) {
// permutacija je cela popunjena, pa je ispisujemo
if (i == a.size())
obradi(a);
else {
// na poziciju i stavljamo redom svaki neupotrebljen
// element
for (int x = 1; x <= n; x++)
if(!upotrebljen[x]) {
a[i] = x;
upotrebljen[x] = true;
permutacije(a, n, upotrebljen, i+1);
upotrebljen[x] = false;
}
}
}
// ispisuje sve permutacije skupa {1, ..., n}
void permutacije(int n) {
vector<int> a(n);
vector<bool> upotrebljen(n+1, false);
permutacije(a, n, upotrebljen, 0);
}#include <iostream>
#include <vector>
using namespace std;
// ispisuje permutaciju na standarndi izlaz
void obradi(const vector<int>& permutacija) {
for (int x : permutacija)
cout << x << " ";
cout << endl;
}
// popunjava se permutacija a od pozicije i nadalje elementima
// skupa {1, ..., n} pri cemu se u nizu upotrebljen beleze
// upotrebljeni elementi u delu permutacije pre pozicije i
void permutacije(vector<int>& a, int n,
vector<bool>& upotrebljen, int i) {
// permutacija je cela popunjena, pa je ispisujemo
if (i == a.size())
obradi(a);
else {
// na poziciju i stavljamo redom svaki neupotrebljen
// element
for (int x = 1; x <= n; x++)
if(!upotrebljen[x]) {
a[i] = x;
upotrebljen[x] = true;
permutacije(a, n, upotrebljen, i+1);
upotrebljen[x] = false;
}
}
}
// ispisuje sve permutacije skupa {1, ..., n}
void permutacije(int n) {
vector<int> a(n);
vector<bool> upotrebljen(n+1, false);
permutacije(a, n, upotrebljen, 0);
}
int main() {
int n;
cin >> n;
permutacije(n);
return 0;
}Ako se odreknemo uslova da permutacije budu uređene leksikografski, nije neophodno vršiti proveru da li je tekući element već upotrebljen tj. možemo postupiti na sledeći način.
Na poslednju poziciju u nizu u kojem čuvamo tekuću permutaciju treba da postavljamo jedan po jedan element skupa, a zatim da rekurzivno određujemo sve permutacije preostalih elemenata (alternativno bismo mogli da krenemo i od prve pozicije). Time se na svakom nivou rekurzije razlikuju prefiks permutacije koji sadrži elemente koje tek treba permutovati i sufiks permutacije koji sadrži elemente koji su fiksirani i već se nalaze na svojim pozicijama. Fiksirane elemente i elemente koje treba permutovati možemo čuvati u istom nizu. Neka na pozicijama \([0, k)\) čuvamo elemente koje treba permutovati, a na pozicijama \([k, n)\) čuvamo fiksirane elemente. Rekurzivna funkcija, dakle, prima niz, i broj \(k\) i pokušava da fiksiran sufiks elemenata na pozicijama \([k, n)\) na sve moguće načine proširi permutacijama elemenata na pozicijama \([0, k)\).
Ako je \(k = 1\), tada postoji samo jedna permutacija jednočlanog niza na poziciji \(0\), nju pridružujemo fiksiranim elementima (pošto je ona već na mestu \(0\) nema potrebe ništa dodatno raditi) i obrađujemo je (tj. ispisujemo).
Ako je \(k > 1\), tada je situacija komplikovanija. Razmotrimo poziciju \(k-1\). Jedan po jedan element dela niza sa pozicija \([0, k)\) treba da dovodimo na mesto \(k-1\) i da rekurzivno pozivamo permutovanje dela niza na pozicijama \([0, k-1)\). Ideja koja se prirodno javlja je da vršimo razmenu elementa na poziciji \(k-1\) redom sa svim elementima iz intervala \([0, k)\) i da nakon svake razmene vršimo rekurzivne pozive.
Primer 6.A.2. Na primer, ako je niz na početku \(123\), onda menjamo element \(3\) sa elementom \(1\), dobijamo \(321\) i pozivamo rekurzivno generisanje permutacija niza \(32\) sa fiksiranim elementom \(1\) na kraju. Zatim u početnom nizu menjamo element \(3\) sa elementom \(2\), dobijamo \(132\) i pozivamo rekurzivno generisanje permutacija niza \(13\) sa fiksiranim elementom \(2\) na kraju. Zatim u početnom nizu menjamo element \(3\) sa samim sobom, dobijamo \(123\) i pozivamo rekurzivno generisanje permutacija niza \(12\) sa fiksiranim elementom \(3\) na kraju.
Ovaj postupak je prikazan i na slici.
Međutim, sa tim pristupom može biti problema. Naime, da bismo bili sigurni da će na poslednju poziciju stizati svi elementi niza, razmene moramo da vršimo u odnosu na početno stanje niza. Jedan način je da se pre svakog rekurzivnog poziva pravi kopija niza, ali postoji i efikasnije rešenje. Naime, možemo kao invarijantu funkcije nametnuti da je nakon svakog rekurzivnog poziva raspored elemenata u nizu isti kao pre poziva funkcije. Ujedno to treba da bude i invarijanta petlje u kojoj se vrše razmene. Na ulasku u petlju raspored elemenata u nizu biće isti kao na ulasku u funkciju. Vršimo prvu razmenu, rekurzivno pozivamo funkciju i na osnovu invarijante rekurzivne funkcije znamo da će raspored nakon rekurzivnog poziva biti isti kao pre njega. Da bismo održali invarijantu petlje, potrebno je niz vratiti u početno stanje. Međutim, znamo da je niz promenjen samo jednom razmenom, tako da je dovoljno uraditi istu tu razmenu i niz će biti vraćen u početno stanje. Time je invarijanta petlje očuvana i može se preći na sledeću poziciju. Kada se petlja završi, na osnovu invarijante petlje znaćemo da je niz isti kao na ulazu u funkciju. Na osnovu toga znamo i da će invarijanta funkcije biti održana i nije potrebno uraditi ništa dodatno nakon petlje.
void obradiSvePermutacije(vector<int>& permutacija, int k) {
if (k == 1)
obradi(permutacija);
else {
for (int i = 0; i < k; i++) {
swap(permutacija[i], permutacija[k-1]);
obradiSvePermutacije(permutacija, k-1);
swap(permutacija[i], permutacija[k-1]);
}
}
}
void obradiSvePermutacije(int n) {
vector<int> permutacija(n);
for (int i = 1; i <= n; i++)
permutacija[i-1] = i;
obradiSvePermutacije(permutacija, n);
}#include <iostream>
#include <vector>
using namespace std;
// ispisuje permutaciju na standarndi izlaz
void obradi(const vector<int>& permutacija) {
for (int x : permutacija)
cout << x << " ";
cout << endl;
}
void obradiSvePermutacije(vector<int>& permutacija, int k) {
if (k == 1)
obradi(permutacija);
else {
for (int i = 0; i < k; i++) {
swap(permutacija[i], permutacija[k-1]);
obradiSvePermutacije(permutacija, k-1);
swap(permutacija[i], permutacija[k-1]);
}
}
}
void obradiSvePermutacije(int n) {
vector<int> permutacija(n);
for (int i = 1; i <= n; i++)
permutacija[i-1] = i;
obradiSvePermutacije(permutacija, n);
}
int main() {
int n;
cin >> n;
obradiSvePermutacije(n);
return 0;
}U jeziku C++ funkcija next_permutation deklarisana u zaglavlju <algorithm> određuje narednu permutaciju u odnosu na datu. Funkciji se prosleđuju dva iteratora koji ograničavaju raspon elemenata u kojima se nalazi permutacija.
// inicijalizujemo permutaciju na 1, 2, ..., n
vector<int> permutacija(n);
for (int i = 0; i < n; i++)
permutacija[i] = i+1;
// ispisujemo permutaciju i trazimo narednu,
// sve dok naredna postoji
do {
obradi(permutacija);
} while (next_permutation(begin(permutacija),
end(permutacija)));#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
// ispisuje permutaciju na standarndi izlaz
void obradi(const vector<int>& permutacija) {
for (int x : permutacija)
cout << x << " ";
cout << endl;
}
int main() {
int n;
cin >> n;
// inicijalizujemo permutaciju na 1, 2, ..., n
vector<int> permutacija(n);
for (int i = 0; i < n; i++)
permutacija[i] = i+1;
// ispisujemo permutaciju i trazimo narednu,
// sve dok naredna postoji
do {
obradi(permutacija);
} while (next_permutation(begin(permutacija),
end(permutacija)));
}Particije broja \(n\) predstavljaju razlaganje tog broja na sabirke čija je vrednost između \(1\) i \(n\). Na primer, broj \(10\) se može particionisati kao \(5 + 2 + 2 + 1\). Svaka particija se može normalizovati tako što se pretpostavi, na primer, da su sabirci sortirani nerastuće. Napisati program koji za datu particiju određuje sledeću particiju u leksikografskom redosledu.
Sa standardnog ulaza se unosi normalizovana particija pri čemu su sabirci razdvojeni karakterom + (njihov zbir je manji od 1000).
Na standardni izlaz ispisati narednu normalizovanu particiju u leksikografskom redosledu (u jednoj liniji, pri čemu su sabirci razdvojeni karakterom +) ili reč ne ako takva particija ne postoji.
5+2+2+1
5+3+1+1
Da bismo dobili sledeću particiju u leksikografskom redosledu, potrebno je uvećati za jedan neki element koji je što bliži kraju niza, dok prefiks niza treba da ostane nepromenjen. Ako je particija jednočlana, tada je ona leksikografski najveća. Poslednji element niza nije moguće povećati za jedan, jer bi zbog očuvanja zbira elemenata particije neki element pre njega morao biti smanjen. Naredni kandidat za povećanje je pretposlednji element, a on se može uvećati na jedan samo ako se na mestu ispred njega ne nalazi element koji mu je jednak, jer bi se tada povećanjem pretposlednjeg elementa dobila particija koja nije normalizovana (uređena nerastući). U suprotnom razmatramo element pre pretposlednjeg i tako redom, sve dok ne naiđemo na element ispred kojeg ne stoji element koji mu je jednak. Taj element povećavamo za 1. Nakon toga potrebno je popraviti elemente iza tog uvećanog elementa, tako da particija bude leksikografski što manja. To će se desiti ako se iza uvećanog elementa postave samo jedinice. Da se zbir ne bi promenio, broj postavljenih jedinica treba da bude za jedan manji od zbira svih elemenata iza elementa koji smo uvećali za jedan (taj zbir možemo izraunavati dok obilazimo niz unazad tražeći najdešnji element koji se može uvećati za 1).
Pošto se dužina particije može promeniti prilikom prelaska na sledeću particiju, umesto klasičnog niza particiju možemo predstaviti nekim oblikom niza koji dopušta dodavanje elemenata na kraj.
bool sledecaParticija(vector<int>& particija)
{
int k = particija.size();
// ako je tekuca particija jednoclana, ne postoji sledeca
if (k == 1)
return false;
// pronalazimo poziciju prvog elementa zdesna koji se moze
// uvecati i ujedno racunamo zbir elemenata iza njega
int i;
int zbir = particija[k-1];
for (i = k-2; i > 0 && particija[i] == particija[i-1]; i--)
zbir += particija[i];
// uklanjamo sve elemente iza pozicije i
particija.resize(i+1);
// uvecavamo element koji smemo uvecati
particija[i]++;
// dodajemo jedinice do kraja particije
for (int m = 0; m < zbir - 1; m++)
particija.push_back(1);
return true;
}
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
bool sledecaParticija(vector<int>& particija)
{
int k = particija.size();
// ako je tekuca particija jednoclana, ne postoji sledeca
if (k == 1)
return false;
// pronalazimo poziciju prvog elementa zdesna koji se moze
// uvecati i ujedno racunamo zbir elemenata iza njega
int i;
int zbir = particija[k-1];
for (i = k-2; i > 0 && particija[i] == particija[i-1]; i--)
zbir += particija[i];
// uklanjamo sve elemente iza pozicije i
particija.resize(i+1);
// uvecavamo element koji smemo uvecati
particija[i]++;
// dodajemo jedinice do kraja particije
for (int m = 0; m < zbir - 1; m++)
particija.push_back(1);
return true;
}
int main() {
vector<int> particija;
while (true) {
int x;
cin >> x;
particija.push_back(x);
char c = cin.get();
if (c != '+')
break;
}
if (sledecaParticija(particija)) {
cout << particija[0];
for (int i = 1; i < particija.size(); i++)
cout << "+" << particija[i];
cout << endl;
} else
cout << "ne" << endl;
return 0;
}Particije broja \(n\) predstavljaju razlaganje tog broja na sabirke čija je vrednost između \(1\) i \(n\). Na primer, broj \(10\) se može particionisati kao \(5 + 2 + 2 + 1\). Svaka particija se može normalizovati tako što se pretpostavi, na primer, da su sabirci sortirani nerastuće. Napiši program koji ispisuje sve particije datog broja.
Sa standardnog ulaza se učitava broj \(n\) (\(1 \leq n \leq 25\)).
Na standardni izlaz ispisati sve normalizovane particije broja \(n\), sortirane leksikografski rastuće.
5
1 1 1 1 1 2 1 1 1 2 2 1 3 1 1 3 2 4 1 5
Svaka particija ima svoj prvi sabirak. Svakoj particiji broja \(n\) kojoj je prvi sabirak \(s\) (pri čemu je \(1 \leq s \leq n\)) jednoznačno odgovara neka particija broja \(n-s\), što ukazuje da se problem može rešavati induktivno-rekurzivnom konstrukcijom. Pošto je sabiranje komutativno, da ne bismo suštinski iste particije ponavljali više puta nametnućemo uslov da sabirci u svakoj particiji budu sortirani nerastuće. Dakle, ako je prvi sabirak \(s\), svi sabirci iza njega moraju da budu manji ili jednaki od \(s\). Zato nam nije dovoljno samo da umemo da generišemo sve particije broja \(n-s\), već je potrebno da ojačamo induktivnu hipotezu. Pretpostavićemo da se u datom vektoru na pozicijama \([0, i)\) nalaze ranije postavljeni elementi particije i da je zadatak procedure da taj niz dopuni na sve moguće načine particijama broja \(n\) u kojima su svi sabirci manji ili jednaki \(s_{max}\). Izlaz iz rekurzije predstavljaće slučaj \(n=0\) u kom je jedina moguća particija broja \(0\) prazan skup, u kome nema sabiraka. Tada smatramo da je particija uspešno formirana i obrađujemo sadržaj vektora.
Jedan način da se particije dopune je da se razmotre sve moguće varijante za sabirak na poziciji \(i\). Na osnovu uslova oni moraju biti veći od nule, manji ili jednaki \(s_{max}\), a prirodno je da moraju da budu i manji ili jednaki od \(n\) (jer prvi sabirak ne može biti veći od zbira prirodnih brojeva). Ako je \(m\) manji od brojeva \(n\) i \(s_{max}\), mogući prvi sabirci su svi brojevi \(1 \leq s' \leq m\). Kada fiksiramo sabirak \(s'\) niz rekurzivno dopunjavamo svim particijama broja \(n-s'\) u kojima su svi sabirci manji ili jednaki \(s'\), jer je potrebno preostali deo zbira predstaviti kao particiju brojeva koji nisu veći od \(s'\).
U glavnoj funkciji ćemo alocirati niz dužine \(n\) (jer najduža particija ima \(n\) sabiraka koji su svi jednaki \(1\)) i zahtevaćemo da se taj niz popuni počevši od pozicije \(0\) particijama broja \(n\) u kojima su svi sabirci manji ili jednaki \(n\).
void obradiParticije(int n, int smax, vector<int>& particija,
int k) {
if (n <= 0)
obradi(particija, k);
else {
for (int s = 1; s <= min(n, smax); s++) {
particija[k] = s;
obradiParticije(n-s, s, particija, k+1);
}
}
}
void obradiParticije(int n) {
vector<int> particija(n);
obradiParticije(n, n, particija, 0);
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void obradi(const vector<int>& particija, int k) {
for (int i = 0; i < k; i++)
cout << particija[i] << " ";
cout << endl;
}
void obradiParticije(int n, int smax, vector<int>& particija,
int k) {
if (n <= 0)
obradi(particija, k);
else {
for (int s = 1; s <= min(n, smax); s++) {
particija[k] = s;
obradiParticije(n-s, s, particija, k+1);
}
}
}
void obradiParticije(int n) {
vector<int> particija(n);
obradiParticije(n, n, particija, 0);
}
int main() {
int n;
cin >> n;
obradiParticije(n);
return 0;
}Umesto da se analiziraju sve moguće vrednosti sabirka na poziciji \(i\), moguće je razmatrati samo dve mogućnosti: prvu da se na poziciji \(i\) javlja sabirak \(s_{max}\), a drugu da se na poziciji \(i\) javlja neki sabirak strogo manji od \(s_{max}\). Prvi slučaj je moguć samo ako je \(n \geq s_{max}\) i kada se na poziciju \(i\) postavi \(s_{max}\) niz dopunjujemo od pozicije \(i+1\) particijama broja \(n-s_{max}\) u kojima su svi sabirci manji ili jednaki \(s_{max}\). Drugi slučaj je uvek moguć i tada particiju dopunjujemo particijama broja \(n\) u kojima je najveći sabirak \(s_{max} - 1\). U zavisnosti od redosleda ova dva rekurzivna poziva određuje se da li će permutacije biti sortirane leksikografski rastuće ili opadajuće.
void obradiParticije(int n, int smax, vector<int>& particija,
int k) {
if (n == 0)
obradi(particija, k);
else {
if (smax == 0) return;
obradiParticije(n, smax-1, particija, k);
if (smax <= n) {
particija[k] = smax;
obradiParticije(n-smax, smax, particija, k+1);
}
}
}
void obradiParticije(int n) {
vector<int> particija(n);
obradiParticije(n, n, particija, 0);
}#include <iostream>
#include <vector>
using namespace std;
void obradi(const vector<int>& particija, int k) {
for (int i = 0; i < k; i++)
cout << particija[i] << " ";
cout << endl;
}
void obradiParticije(int n, int smax, vector<int>& particija,
int k) {
if (n == 0)
obradi(particija, k);
else {
if (smax == 0) return;
obradiParticije(n, smax-1, particija, k);
if (smax <= n) {
particija[k] = smax;
obradiParticije(n-smax, smax, particija, k+1);
}
}
}
void obradiParticije(int n) {
vector<int> particija(n);
obradiParticije(n, n, particija, 0);
}
int main() {
int n;
cin >> n;
obradiParticije(n);
return 0;
}Još jedan način da se reši zadatak je da se iterativno nabrajaju sledeće particije u leksikografskom redosledu (krenuvši od particije koja ima \(n\) jedinica) sve dok se ne dođe do poslednje particije koja sadrži samo broj \(n\). Pronalaženje sledeće particije u leksikografskom redosledu moguće je uraditi funkcijom koja je opisana u zadatku [Sledeća particija].
void obradiParticije(int n) {
vector<int> particija(n, 1);
int k = n;
do {
obradi(particija, k);
} while (sledecaParticija(particija, k));
}#include <iostream>
#include <vector>
using namespace std;
void obradi(const vector<int>& particija, int k) {
for (int i = 0; i < k; i++)
cout << particija[i] << " ";
cout << endl;
}
bool sledecaParticija(vector<int>& particija, int& k) {
// ako je tekuca particija jednoclana, ne postoji sledeca
if (k == 1)
return false;
// pronalazimo poziciju prvog elementa zdesna koji se moze uvecati i
// ujedno racunamo zbir elemenata iza njega
int i;
int zbir = particija[k-1];
for (i = k-2; i > 0 && particija[i] == particija[i-1]; i--)
zbir += particija[i];
// uvecavamo element koji smemo uvecati
particija[i]++;
// postavljamo jedinice do kraja particije
for (k = i+1; --zbir > 0; k++)
particija[k] = 1;
return true;
}
void obradiParticije(int n) {
vector<int> particija(n, 1);
int k = n;
do {
obradi(particija, k);
} while (sledecaParticija(particija, k));
}
int main() {
int n;
cin >> n;
obradiParticije(n);
return 0;
}