KOMBINATORNI PROBLEMI- PRIMERI

Kombinatorika - Primeri zadataka

Na ovoj stranici se nalaze različiti primeri zadataka iz kombinatorike. Prva četiri zadatka su ponovljena sa stranice o rekurzivnim algoritmima zbog njihove povezanosti sa ovom temom.

Uvod u kombinatoriku

Kombinatorika je grana matematike koja se bavi proučavanjem načina na koje se elementi mogu rasporediti ili kombinovati. Ključni koncepti uključuju:

Varijacije

Varijacije predstavljaju raspoređivanje k elemenata od ukupno n elemenata pri čemu redosled elemenata igra ulogu. Razlikujemo varijacije sa i bez ponavljanja:

V_n,k = n! / (n - k)!  (bez ponavljanja)
V_n,k = n^k            (sa ponavljanjem)

Permutacije

Permutacije predstavljaju specijalni slučaj varijacija kada se uzima svih n elemenata:

P_n = n!

Ako neki elementi unutar niza nisu različiti, koristi se formula:

P_n = n! / (k1! * k2! * ... * kr!)

Kombinacije

Kombinacije predstavljaju biranje k elemenata od n elemenata, pri čemu redosled nije bitan:

C_n,k = n! / (k! * (n - k)!)

Ako je dozvoljeno ponavljanje elemenata, koristi se formula:

C'_n,k = (n + k - 1)! / (k! * (n - 1)!)

1. Sledeća varijacija

Napomena: Zadatak iz zbirke cpp2-Metodička zbirka iz algoritmike sa sajta petlja.org

Napiši program koji određuje narednu varijaciju dužine k skupa {1, . . . , n} u leksikografskom poretku.

Ulaz:
Prva linija sadrži broj k (1 ≤ k ≤ 100), druga broj n (1 ≤ n ≤ 100). U trećoj liniji se nalazi varijacija opisana brojevima razdvojenim po jednim razmakom.

Izlaz:
Ispisati sledeću varijaciju u leksikografskom poretku ili ako je učitana varijacija leksikografski maksimalna.

Primer:

Ulaz
5
4
1 1 2 3 4

Izlaz
1 1 2 4 1

Napiši program koji određuje narednu varijaciju dužine k skupa {1, ..., n} u leksikografskom poretku.

Ulaz:

Prva linija: broj k (1 ≤ k ≤ 100)
Druga linija: broj n (1 ≤ n ≤ 100)
Treća linija: varijacija od k brojeva (od 1 do n)

Izlaz:

Ako postoji naredna varijacija: ispisati je.
Ako je uneta varijacija leksikografski poslednja: ispisati -.

Primer ulaza:
5
4
1 1 2 3 4

Primer izlaza:
1 1 2 4 1

#include <iostream>
#include <vector>

using namespace std;

bool sledecaVarijacija(vector<int>& varijacija, int n) {
  int k = varijacija.size();
  int poz = k - 1;

  while (poz >= 0 && varijacija[poz] == n) {
    varijacija[poz] = 1;
    poz--;
  }

  if (poz < 0) return false;

  varijacija[poz]++;
  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(varijacija, n)) {
    for (int x : varijacija)
      cout << x << " ";
    cout << endl;
  } else {
    cout << "-" << endl;
  }

  return 0;
}

2. Sve varijacije

Napomena: Zadatak iz zbirke cpp2-Metodička zbirka iz algoritmike sa sajta petlja.org

Napiši program koji određuje sve varijacije sa ponavljanjem dužine k skupa {1, . . . , n}.

Ulaz:
Sa standardnog ulaza se učitava broj n (1 ≤ n ≤ 5) i u narednoj liniji broj k (1 ≤ k ≤ 5).

Izlaz:
Ispisati sve varijacije, sortirane leksikografski.

Primer:

Ulaz
2
3

Izlaz
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 sa ponavljanjem od n elemenata k-te klase generišu se tako što se prvo menjaju cifre sa desne strane dok se ne dođe do kraja skupa. Nakon toga, povećava se vrednost na susednoj poziciji ulevo i vrednosti desno se resetuju na prvi element skupa.

#include <iostream>
using namespace std;
void generisiVarijacije(int n, int k, vector<int> &varijacija) {

// Ako smo popunili varijaciju, ispisujemo je
if (varijacija.size() == k) {

for (int broj : varijacija) {

cout << broj << " ";

}
cout << endl;
return;

}
// Dodavanje sledećeg elementa u varijaciju
for (int i = 1; i <= n; i++) {

varijacija.push_back(i);
generisiVarijacije(n, k, varijacija);
varijacija.pop_back(); // Vraćanje u prethodno stanje

}
}

int main() {

int N, K;
cin >> N >> K;
vector<int> varijacija;
generisiVarijacije(N, K, varijacija);
return 0;

}

3. Sve reči od datih slova

Stringom s dat je skup malih slova engleskog alfabeta i prirodan broj k. Napisati program koji prikazuje sve reči dužine k u leksikografskom poretku.

Ulaz:
Prva linija sadrži string s dužine najviše 10, druga linija broj k (k ≤ 6, k ≤ n).

Izlaz:
Ispisati sve tražene reči u leksikografskom poretku, svaku u posebnoj liniji.

Primer:

Ulaz
amx
2

Izlaz
aa
am
ax
ma
mm
mx
xa
xm
xx

4. Svi podskupovi

Napiši program koji ispisuje sve podskupove datog skupa.

Ulaz:
Sa standardnog ulaza se učitava broj n (3 ≤ n ≤ 10), a zatim n prirodnih brojeva, rastuće sortiranih.

Izlaz:
Ispisati sve podskupove skupa, svaki u posebnom redu, sa elementima razdvojenim jednim razmakom.

Primer:

Ulaz
3
1 2 3

Izlaz
3
2
2 3
1
1 3
1 2
1 2 3

5. Sledeći podskup

Napiši program koji određuje podskup skupa brojeva {1, . . . , n} koji u leksikografskom redosledu sledi neposredno iza datog podskupa. Podskupovi su zadati u obliku strogo rastuće sortiranih nizova.

Ulaz:
Prva linija sadrži broj n (1 ≤ n ≤ 100), a naredna linija sadrži podskup čiji su elementi zadati sortirano rastuće, razdvojeni po jednim razmakom.
Izlaz:
Na standardni izlaz u jednoj liniji ispisati elemente traženog podskupa tj. - ako je učitani
podskup leksikografski najveći.
Primer
Ulaz
5
1 2 3 4 5
Izlaz
1 2 3 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...

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

void sledeci_podskup(int n, vector<int>& podskup) {
int k = podskup.size();

// Pronalaženje prve pozicije s desna gde možemo povećati broj
int i = k - 1;
while (i >= 0 && podskup[i] == n - (k - 1 - i)) {
i--;
}

// Ako ne postoji sledeći podskup (tj. ovo je poslednji podskup)
if (i < 0) {
cout << "-" << endl;
return;
}

// Povećavamo broj na poziciji i
podskup[i]++;

// Svi naredni brojevi postaju uzastopni
for (int j = i + 1; j < k; j++) {
podskup[j] = podskup[j - 1] + 1;
}

// Ispis rezultata
for (int x : podskup) {
cout << x << " ";
}
cout << endl;
}

int main() {
int n;
cin >> n;
cin.ignore(); // Ignorišemo preostali novi red nakon broja n

string linija;
getline(cin, linija); // Učitavamo ceo red sa podskupom

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

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

// Poziv funkcije za nalaženje sledećeg podskupa
sledeci_podskup(n, podskup);

return 0;
}

6: Sledeći binarni niz bez susednih jedinica

Posmatrajmo leksikografski poređane binarne nizove dužine n koji sadrže nule i jedinice, ali ne sadrže dve susedne jedinice. Na primer, takvi nizovi dužine 3 su: 000, 001, 010, 100 i 101. Napiši program koji za dati niz određuje naredni niz u leksikografskom poretku.

Ulaz:

Sa standardnog ulaza se učitava binarni niz bez uzastopnih jedinica dužine n (1 ≤ n ≤ 50). Svi elementi su zapisani jedan iza drugog, bez razmaka.

Izlaz:

Jedina linija standardnog izlaza treba da sadrži elemente narednog niza u leksikografskom poretku (ispisane jedan iza drugog, bez razmaka) ili tekst ne postoji ako je učitani niz leksikografski najveći.

Primer 1

Ulaz

10101000100001010

Izlaz

10101000100010000

Primer 2

Ulaz

10101010

Izlaz

ne postoji

Napiši program koji određuje naredni binarni niz bez susednih jedinica u leksikografsom poretku. Koraci rešenja:

Implementirati funkciju isValid koja proverava da li niz ne sadrži podniz "11".
Implementirati funkciju incrementString koja uvećava binarni niz (poput binarnog sabiranja).
Implementirati funkciju maxValid koja generiše maksimalni validni niz dužine n (na parnim pozicijama '1', a na neparnim '0').
U funkciji main, ako je ulazni niz jednak maksimalnom validnom nizu, ispisati ne postoji; inače, inkrementirati ulazni niz dok se ne pronađe validan niz i ispisati ga.

#include <iostream>
#include <string>
// Koristi se za rad sa stringovima i ulaz/izlaz
using namespace std;

// Funkcija koja proverava da li binarni niz ne sadrži susedne jedinice
bool isValid(const string& s) {
  return s.find("11") == string::npos;
}

// Funkcija koja "uvećava" binarni niz (poput binarnog sabiranja)
// Pretpostavljamo da niz ima fiksnu dužinu
string incrementString(string s) {
  int i = s.size() - 1;
  while (i >= 0 && s[i] == '1') {
    s[i] = '0';
    i--;
  }
  if (i >= 0) {
    s[i] = '1';
  }
  return s;
}

// Funkcija koja vraća maksimalni validni binarni niz dužine n bez susednih jedinica
string maxValid(int n) {
  string maxs;
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0)
      maxs.push_back('1');
    else
      maxs.push_back('0');
  }
  return maxs;
}

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;

  string maxs = maxValid(n);

  if (s == maxs) {
    cout << "ne postoji" << endl;
    return 0;
  }

  string candidate = s;
  do {
    candidate = incrementString(candidate);
  } while (!isValid(candidate));

  cout << candidate << endl;
  return 0;
}

7. Zadatak: Brojevi koji u binarnom zapisu nemaju dve susedne nule

Napisati program kojim se prikazuju dekadni zapisi svih prirodnih brojeva koji u binarnom sistemu imaju najviše n binarnih cifara i nemaju dve uzastopne nule.

Ulaz:

Prva linija standardnog ulaza sadrži prirodan broj n (1 ≤ n ≤ 20).

Izlaz:

Na standardnom izlazu prikazati tražene brojeve u rastućem poretku, svaki broj u posebnoj liniji.

Primer

Ulaz

Izlaz

Zadatak 8: Sledeća kombinacija

Napomena: Zadatak iz zbirke cpp2 – Metodička zbirka iz algoritmike sa sajta petlja.org

Napiši program koji određuje sledeću kombinaciju dužine k skupa {1, ..., n} u leksikografskom poretku.

Ulaz:
Prva linija sadrži broj k (1 ≤ k ≤ 100), druga broj n (1 ≤ n ≤ 100). U trećoj liniji se nalazi kombinacija opisana brojevima razdvojenim po jednim razmakom.

Izlaz:
Ispisati sledeću kombinaciju u leksikografskom poretku ili ako je učitana kombinacija leksikografski maksimalna, ispisati "-".

Primer:

Ulaz
4
5
1 2 3 4

Izlaz
1 2 3 5

Napiši program koji određuje sledeću kombinaciju dužine k skupa {1, ..., n} u leksikografskom poretku.

Ulaz:

Prva linija: broj k (1 ≤ k ≤ 100)
Druga linija: broj n (1 ≤ n ≤ 100)
Treća linija: kombinacija od k brojeva (od 1 do n)

Izlaz:

Ako postoji sledeća kombinacija: ispisati je.
Ako je uneta kombinacija leksikografski poslednja: ispisati -.

Primer ulaza:
4
5
1 2 3 4

Primer izlaza:
1 2 3 5

Primer 2

Ulaz
3
5
1 3 4

Izlaz
1 3 5

Primer 3

Ulaz
3
5
1 3 5

Izlaz
1 4 5

Primer 4

Ulaz
3
5
3 4 5

Izlaz
-

#include <iostream>
#include <vector>

using namespace std;

bool sledecaKombinacija(vector<int>& kombinacija, int n) {
  int k = kombinacija.size();
  int poz = k - 1;

  while (poz >= 0 && kombinacija[poz] == n - (k - 1 - poz)) {
    kombinacija[poz] = kombinacija[poz - 1] + 1;
    poz--;
  }

  if (poz < 0) return false;

  kombinacija[poz]++;
  return true;
}

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

  vector<int> kombinacija(k);
  for (int i = 0; i < k; i++) {
    cin >> kombinacija[i];
  }

  if (sledecaKombinacija(kombinacija, n)) {
    for (int x : kombinacija)
      cout << x << " ";
    cout << endl;
  } else {
    cout << "-" << endl;
  }

  return 0;
}

Zadatak 9: Sledeća varijacija bez ponavljanja

Napomena: Zadatak iz zbirke cpp2–Metodička zbirka iz algoritmike sa sajta petlja.org

Napiši program koji određuje narednu varijaciju dužine k skupa {1, …, n} u leksikografsom poretku.

Ulaz:
Prva linija standardnog ulaza sadrži broj k (1 ≤ k ≤ 100), druga broj n (1 ≤ n ≤ 100). U trećoj liniji se nalazi varijacija opisana brojevima razdvojenim po jednim razmakom.

Izlaz:
Ispisati sledeću varijaciju u leksikografsom poretku, ako ona postoji, ili ispisati - ako je učitana varijacija leksikografski maksimalna.

Primer:

Ulaz
5
4
1 3 2 4

Izlaz
1 3 2 5

Napiši program koji određuje narednu varijaciju dužine k skupa {1, …, n} u leksikografsom poretku.

Ulaz:

Prva linija: broj k (1 ≤ k ≤ 100)
Druga linija: broj n (1 ≤ n ≤ 100)
Treća linija: varijacija od k brojeva (iz skupa {1, …, n})

Izlaz:

Ako postoji sledeća varijacija: ispisati je.
Ako je učitana varijacija leksikografski poslednja: ispisati -.

Primer ulaza:
5
4
1 3 2 4

Primer izlaza:
1 3 2 5


#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;




/* Proverava da li postoji neupotrebljen element iz skupa {1, …, n} koji je veći od datog elementa */


bool imaUSkupu(int element, int n, const vector& uzeteVrednosti) {
    
  auto it = uzeteVrednosti.begin() + element + 1; // Traži od sledećeg indeksa
    
  while ((it = find(it, uzeteVrednosti.begin() + n + 1, false)) != uzeteVrednosti.begin() + n + 1) {
        
    int slobodanElement = distance(uzeteVrednosti.begin(), it);
        
    if (slobodanElement <= n) return true;
        
    ++it;
    
  }
    
  return false;

}


/* Funkcija koja traži sledeću leksikografski varijaciju */


bool sledecaVarijacija(vector& varijacija, vector& uzeteVrednosti, int n) {
    
  int k = varijacija.size();
    
  int poz = k - 1; // Početak od poslednje pozicije
    
  while (poz >= 0 && !imaUSkupu(varijacija[poz], n, uzeteVrednosti)) {
        
    uzeteVrednosti[varijacija[poz]] = false;  // Oslobađa se element jer se traži zamena
        
    poz--;
    
  }
    
  if (poz < 0) return false; // Nema pozicije za zamenu
    
  // Oslobađa se trenutni element pre traženja zamene
    
  uzeteVrednosti[varijacija[poz]] = false;
    
  auto it = uzeteVrednosti.begin() + varijacija[poz] + 1;
    
  while ((it = find(it, uzeteVrednosti.begin() + n + 1, false)) != uzeteVrednosti.begin() + n + 1) {
        
    int novi = distance(uzeteVrednosti.begin(), it);
        
    if (novi <= n) {
            
      varijacija[poz] = novi;
            
      uzeteVrednosti[novi] = true;
            
      break;
        
    }
        
    ++it;
    
  }
    
  for (int i = poz + 1; i < k; i++) {
        
    auto it = find(uzeteVrednosti.begin() + 1, uzeteVrednosti.begin() + n + 1, false);
        
    if (it != uzeteVrednosti.begin() + n + 1) {
            
      int slobEl = distance(uzeteVrednosti.begin(), it);
            
      varijacija[i] = slobEl;
            
      uzeteVrednosti[slobEl] = true;
        
    }
    
  }
    
  return true;

}


int main() {
    
  int k, n;
    
  cin >> k >> n;
    
  bool imaSledece = false;
    
  vector<int> varijacija(k);
    
  vector<bool> uzeteVrednosti(n + 1, false);
    
  for (int i = 0; i < k; i++) {
        
    cin >> varijacija[i];
        
    uzeteVrednosti[varijacija[i]] = true; // Označi da je taj broj zauzet
    
  }
    
  if (sledecaVarijacija(varijacija, uzeteVrednosti, n)) {
        
    for (int c : varijacija) {
            
      cout << c << " ";
        
    }
        
    cout << endl;
    
  } else {
        
    cout << "-" << endl;
    
  }
    
  return 0;

}

Zadatak 10: Sve kombinacije sa ponavljanjem

Napiši program koji generiše i ispisuje sve kombinacije dužine K elemenata iz skupa {1, 2, …, N} (sa ponavljanjem) u leksikografsom poretku.

Ulaz:
Prva linija sadrži dva broja: N (maksimalna vrednost elementa) i K (dužina kombinacije).

Izlaz:
Na standardni izlaz ispisati sve kombinacije sa ponavljanjem, svaku u posebnoj liniji.

Primer:

Ulaz
5 3

Izlaz
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 2 1
1 2 2
… (ostale kombinacije)

Napiši program koji generiše sve kombinacije sa ponavljanjem dužine K iz skupa {1, …, N} u leksikografsom poretku. Postupak rešenja:

Definiši funkciju obradi koja ispisuje trenutnu kombinaciju.
Implementiraj rekurzivnu funkciju sledecaKombinacija koja popunjava niz kombinacije pozicijama od 0 do K-1. Za prvi element koristi vrednost 1, a za ostale koristi vrednost prethodnog elementa – time se dozvoljava ponavljanje.
Kada se popune svih K elemenata, funkcija obradi se poziva da ispiše kombinaciju.
Pozovi funkciju sveKombinacije koja pokreće generisanje kombinacija.

Primer ulaza:
5 3

Primer izlaza:
1 1 1
1 1 2
1 1 3
…


#include <iostream>
#include <vector>


using namespace std;



/* Funkcija za ispis trenutne kombinacije */


void obradi(const vector<int>& kombinacija) {

  for (int v : kombinacija) {

    cout << v << " ";

  }

  cout << "\\n";

}



/* Rekurzivna funkcija za generisanje kombinacija sa ponavljanjem */


void sledecaKombinacija(vector<int>& kombinacija, int poz, int N, int K) {

  if (poz == K) { // Ako su popunjene sve pozicije, ispisuje se kombinacija

    obradi(kombinacija);

    return;

  }



  // Po\u010dinje se od vrednosti 1 za prvi element ili od prethodnog elementa za ostale

  int start = (poz == 0) ? 1 : kombinacija[poz - 1];



  for (int i = start; i <= N; i++) {

    kombinacija[poz] = i;

    sledecaKombinacija(kombinacija, poz + 1, N, K);

  }

}



/* Funkcija koja pokreće generisanje svih kombinacija */


void sveKombinacije(int N, int K) {

  vector<int> kombinacija(K, 1);

  sledecaKombinacija(kombinacija, 0, N, K);

}



int main() {

  int N, K;

  cout << "Unesite N i K: ";

  cin >> N >> K;

  sveKombinacije(N, K);

  return 0;

}

Zadatak 11: Sledeca permutacija

Sve permutacije brojeva od 1 do n mogu se poredati leksikografski. Za dati n i dati niz od n brojeva (permutaciju), odrediti sledecu permutaciju u tom poretku. Ako je uneti niz poslednja permutacija, ispisati ne postoji.

Ulaz:
Prva linija sadrzi broj n (n < 1000). U sledecih n redova po jedan element permutacije.

Izlaz:
Na izlaz ispisati elemente sledece permutacije, svaki u posebnom redu, ili u jednom redu poruku ne postoji.

Primer:

Ulaz
5
3
1
4
5
2

Izlaz
3
1
5
2
4

Algoritam za „sledecu permutaciju“ u leksikografskom poretku:

Pronadji najveci indeks i tako da a[i] < a[i+1]. Ako takvog nema, to je poslednja permutacija.
Pronadji najveci indeks j > i tako da a[j] > a[i].
Razmenom a[i] i a[j] pomeris permutaciju na sledeci blok.
Obrni (reverse) segment a[i+1..n-1] da bi dobio najmanju mogucu permutaciju u nastavku.

Primer ulaza:
5
3 1 4 5 2

Primer izlaza:
3 1 5 2 4


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Pronalaženje i ispis sledeće permutacije
bool sledecaPermutacija(vector<int>& a) {
    int n = a.size();
    int i = n - 2;
    while (i >= 0 && a[i] >= a[i+1]) {
        --i;
    }
    if (i < 0) return false;

    int j = n - 1;
    while (a[j] <= a[i]) {
        --j;
    }
    swap(a[i], a[j]);
    reverse(a.begin() + i + 1, a.end());

    for (int x : a) {
        cout << x << "\n";
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    if (!sledecaPermutacija(a)) {
        cout << "ne postoji\n";
    }

    return 0;
}

Zadatak 12: Sve permutacije

Napiši program koji generiše i ispisuje sve permutacije skupa {1, 2, …, n}.

Ulaz:
Sa standardnog ulaza se učitava broj n (1 ≤ n ≤ 8).

Izlaz:
Na standardni izlaz ispisati sve permutacije skupa {1, …, n}. Svaku permutaciju ispisati u posebnoj liniji, elemente razdvojiti jednim razmakom. Redosled permutacija može biti proizvoljan (npr. leksikografski).

Primer:

Ulaz
3

Izlaz
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Postupak rešenja:

Napraviti vektor perm dimenzije n i inicijalizovati ga sa 1,2,…,n. Napraviti i niz used dužine n+1 i označiti sve vrednosti koje su u perm kao zauzete.
Ispisati početnu permutaciju pozivom funkcije obradi (ili direktno u main).
Pozivati funkciju sledecaVarijacija(perm, used, n) koja implementira algoritam za sledeću leksikografsku permutaciju:
- Traži najveći indeks i na kojem možeš da povećaš perm[i], oslobađajući zauzete vrednosti levo.
- Zameni perm[i] sledećim većim slobodnim brojem.
- Popuni pozicije desno od i najnižim mogućim slobodnim brojevima.
Ponoviti ispis permutacije sve dok sledecaVarijacija vraća true.


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Proverava da li u skupu postoji slobodan broj veći od trenutnog elementa
bool imaUSkupu(int element,
                    int n,
                    const vector<bool>& uzeteVrednosti)
{
    // Kreni od pozicije iza trenutnog elementa i traži slobodan (false) element
    auto it = uzeteVrednosti.begin() + element + 1;
    while ((it = find(it, uzeteVrednosti.end(), false)) != uzeteVrednosti.end())
    {
        int slobodanElement = distance(uzeteVrednosti.begin(), it);
        // Ako je pronađeni slobodan broj u granici skupa {1, ..., n}
        if (slobodanElement <= n)
            return true;
        ++it;
    }
    return false;
}

// Funkcija koja generiše sledeću leksikografsku permutaciju
bool sledecaVarijacija(vector<int>& varijacija,
                         vector<bool>& uzeteVrednosti,
                         int n)
{
    int k = varijacija.size();
    int poz = k - 1;

    // Tražimo poziciju s desna na levo koja može da se poveća
    while (poz >= 0 &&
           !imaUSkupu(varijacija[poz], n, uzeteVrednosti))
    {
        // Oslobađamo trenutno zauzetu vrednost
        uzeteVrednosti[varijacija[poz]] = false;
        poz--;
    }

    // Ako nema više permutacija
    if (poz < 0) return false;

    // Oslobađamo i ovu vrednost da bismo je zamenili
    uzeteVrednosti[varijacija[poz]] = false;

    // Pronalazimo najmanji mogući slobodan broj veći od trenutnog
    auto it = uzeteVrednosti.begin() + varijacija[poz] + 1;
    while ((it = find(it, uzeteVrednosti.end(), false)) != uzeteVrednosti.end())
    {
        int novi = distance(uzeteVrednosti.begin(), it);
        if (novi <= n)
        {
            varijacija[poz] = novi;
            uzeteVrednosti[novi] = true;
            break;
        }
        ++it;
    }

    // Popunjavamo desni deo najmanjim slobodnim vrednostima
    for (int i = poz + 1; i < k; i++)
    {
        auto it2 = find(uzeteVrednosti.begin() + 1,
                        uzeteVrednosti.begin() + n + 1,
                        false);
        if (it2 != uzeteVrednosti.begin() + n + 1)
        {
            int slobEl = distance(uzeteVrednosti.begin(), it2);
            varijacija[i] = slobEl;
            uzeteVrednosti[slobEl] = true;
        }
    }

    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // Inicijalizujemo permutaciju 1,2,...,n
    vector<int> perm(n);
    vector<bool> used(n + 1, false);
    for (int i = 0; i < n; i++)
    {
        perm[i] = i + 1;
        used[i + 1] = true;
    }

    // Ispisujemo sve permutacije
    do {
        for (int x : perm)
            cout << x << " ";
        cout << "\\n";
    } while (sledecaVarijacija(perm, used, n));

    return 0;
}

Zadatak 13.: Svi palindromi od date reči

Data je reč r napisana malim slovima engleske abecede. Napisati program kojim se prikazuju u leksikografskom poretku svi palindromi koji se mogu dobiti razmeštanjem slova date reči.

Ulaz:
Prva i jedina linija standardnog ulaza sadrži reč r sa najviše 20 malih slova engleske abecede.

Izlaz:
Na standardnom izlazu prikazati tražene palindrome. Ako se ne može formirati nijedan palindrom, prikazati crticu -.

Primer 1:
Ulaz:
racecar
Izlaz:
acrerca
arcecra
carerac
craearc
racecar
rcaeacr

Primer 2:
Ulaz:
abcdecda
Izlaz:
-

Postupak rešenja:

Palindrom je string koji se čita isto s leva na desno i s desna na levo.
Reč može formirati palindrom ako najviše jedno slovo ima neparan broj ponavljanja.
Pravimo polovinu palindroma (svako slovo uzimamo broj / 2 puta) i generišemo sve jedinstvene permutacije te polovine.
Za svaku permutaciju dodajemo srednji karakter (ako postoji), i obrnutu polovinu – tako se formira ceo palindrom.
Ispisujemo sve dobijene palindrome u leksikografskom poretku.


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

int main() {
    string rec;
    cin >> rec;
    int duzina = rec.size();

    map<char,int> brojPonavljanja;
    for (char c : rec) {
        brojPonavljanja[c]++;
    }

    int neparnih = 0;
    char srednjiKarakter = 0;
    for (auto &par : brojPonavljanja) {
        if (par.second % 2 != 0) {
            neparnih++;
            srednjiKarakter = par.first;
        }
    }

    if (neparnih > 1) {
        cout << "-\n";
        return 0;
    }

    string polovina;
    polovina.reserve(duzina / 2);
    for (auto &par : brojPonavljanja) {
        polovina += string(par.second / 2, par.first);
    }

    sort(polovina.begin(), polovina.end());
    bool ima = false;
    do {
        string palindrom = polovina;
        if (srednjiKarakter) {
            palindrom.push_back(srednjiKarakter);
        }
        palindrom += string(polovina.rbegin(), polovina.rend());

        cout << palindrom << "\n";
        ima = true;
    } while (next_permutation(polovina.begin(), polovina.end()));

    if (!ima) {
        cout << "-\n";
    }

    return 0;
}

Uvod u particije broja `n`

Particija prirodnog broja n je način da ga izrazimo kao sumu pozitivnih cijelih brojeva: n = a₁ + a₂ + … + a_k, gdje su sabirci a₁ ≥ a₂ ≥ … ≥ a_k ≥ 1. Redoslijed sabiraka ne igra ulogu—uvijek ih zapisujemo u nerastućem poretku.

Zašto particije?
Particije se javljaju u kombinatorici, teoriji brojeva, pa čak i u fizici i kriptografiji, kada želimo da istražimo sve moguće načine raspodjele neke količine na dijelove.

Primjer za n = 5:

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

U zadatku “Sve particije” moramo generisati i ispisati upravo ovakav sveobuhvatan popis, sortirajući particije leksikografski u nerastućem (normalizovanom) poretku.

Zadatak 14: Sledeća particija

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 normalizuje tako što su sabirci sortirani nerastuće. Napiši program koji za datu particiju određuje sledeću particiju u leksikografskom redosledu.

Ulaz:
Sa standardnog ulaza se unosi normalizovana particija, sabirci su razdvojeni znakom + (njihov zbir < 1000).

Izlaz:
Ispisati narednu normalizovanu particiju u leksikografskom redosledu (sabirci razdvojeni +), ili reč ne ako takva particija ne postoji.

Primer:

Ulaz
5+2+2+1

Izlaz
5+3+1+1

Postupak rešenja:

Parsiranje ulaza: Učitati celu liniju i pretvoriti sabirke razdvojene + u vektor part.
Traženje sledeće particije: Za i od kraja ka početku:
- Izračunati prefix_sum = suma sabiraka pre i.
- Odrediti max_val = (ako je i==0 onda N, inače part[i-1]).
- Pokušati new_val od part[i]+1 do max_val, izračunati rem = N - prefix_sum - new_val.
- Ako je rem ≥ 0, formirati novu particiju: part[0..i-1], new_val, 1,1,…,1 (rem puta) i ispisati je.
Kraj: Ako nijedna pozicija i nije radila, ispisati ne.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1) Parsiranje ulaza
    string linija;
    if (!getline(cin, linija)) return 0;
    vector<int> part;
    {
        int broj = 0;
        for (char c : linija) {
            if (c == '+') {
                part.push_back(broj);
                broj = 0;
            } else {
                broj = broj * 10 + (c - '0');
            }
        }
        part.push_back(broj);
    }

    int k = part.size();
    int N = accumulate(part.begin(), part.end(), 0);

    // 2) Traženje sledeće particije
    for (int i = k - 1; i >= 0; --i) {
        int prefix_sum = 0;
        for (int j = 0; j < i; ++j) prefix_sum += part[j];
        int max_val = (i == 0 ? N : part[i-1]);

        for (int new_val = part[i] + 1; new_val <= max_val; ++new_val) {
            int rem = N - prefix_sum - new_val;
            if (rem < 0) break;

            vector<int> sledeca;
            sledeca.reserve(i + 1 + rem);
            for (int j = 0; j < i; ++j) sledeca.push_back(part[j]);
            sledeca.push_back(new_val);
            for (int t = 0; t < rem; ++t) sledeca.push_back(1);

            for (int idx = 0; idx < (int)sledeca.size(); ++idx) {
                if (idx) cout << '+';
                cout << sledeca[idx];
            }
            cout << "\n";
            return 0;
        }
    }

    // 3) Ako nema sledeće particije
    cout << "ne\n";
    return 0;
}

Zadatak 15: Sve particije

Particije broja n predstavljaju razlaganje tog broja na sabirke čija je vrednost između 1 i n. Svaku particiju normalizujemo tako što sabirci budu sortirani nerastuće, i ispišemo ih leksikografski rastuće. Napiši program koji za zadati broj n (1 ≤ n ≤ 25) ispisuje sve normalizovane particije broja n.

Ulaz:
Jedan ceo broj n.

Izlaz:
Sve normalizovane particije broja n, po jednoj u liniji, sabirci razdvojeni razmakom.

Primer:

Ulaz
5

Izlaz
1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5

#include <bits/stdc++.h>
using namespace std;

// čuva trenutnu particiju
vector<int> trenutnaParticija;

// ostatakParticij = koliko još treba da pokrijemo,
// maksSabirak    = najveći dozvoljeni sledeći sabirak
void izradaParticije(int ostatakParticij, int maksSabirak) {
    if (ostatakParticij == 0) {
        // ispiši gotovu particiju
        for (int i = 0; i < (int)trenutnaParticija.size(); i++) {
            if (i) cout << ' ';
            cout << trenutnaParticija[i];
        }
        cout << "\n";
        return;
    }
    // biramo sabirak od 1 do min(maksSabirak, ostatakParticij)
    for (int p = 1; p <= maksSabirak && p <= ostatakParticij; ++p) {
        trenutnaParticija.push_back(p);
        // sledeći sabirak mora biti ≤ p da bi particija bila nerastuća
        izradaParticije(ostatakParticij - p, p);
        trenutnaParticija.pop_back();
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int broj;
    cin >> broj;
    izradaParticije(broj, broj);
    return 0;
}

KOMBINATORNI PROBLEMI- PRIMERI

Kombinatorika - Primeri zadataka

Uvod u kombinatoriku

Varijacije

Permutacije

Kombinacije

1. Sledeća varijacija

2. Sve varijacije

3. Sve reči od datih slova

4. Svi podskupovi

5. Sledeći podskup

6: Sledeći binarni niz bez susednih jedinica

Ulaz:

Izlaz:

Primer 1

Primer 2

7. Zadatak: Brojevi koji u binarnom zapisu nemaju dve susedne nule

Ulaz:

Izlaz:

Primer

Ulaz

Izlaz

Zadatak 8: Sledeća kombinacija

Primer 2

Primer 3

Primer 4

Zadatak 9: Sledeća varijacija bez ponavljanja

Zadatak 10: Sve kombinacije sa ponavljanjem

Zadatak 11: Sledeca permutacija

Zadatak 12: Sve permutacije

Zadatak 13.: Svi palindromi od date reči

Uvod u particije broja n

Zadatak 14: Sledeća particija

Zadatak 15: Sve particije

Podešavanja kolačića

Uvod u particije broja `n`