Algoritmi → Rekurzija i bektreking → Generisanje permutacija, kombinacija i varijacija

Generisanje permutacija, kombinacija i varijacija

Pojmovi i broj mogućnosti

Kako se ovi brojevi računaju bez generisanja, objašnjeno je u lekciji Kombinatorika.

Permutacije – rekurzivno

Na svaku poziciju redom stavljamo jedan od još neiskorišćenih brojeva. Niz iskoriscen pamti koji su brojevi već u permutaciji.

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

int n;
vector<int> perm;
vector<bool> iskoriscen;

void generisi() {
    if ((int)perm.size() == n) {               // permutacija je kompletna
        for (int x : perm) cout << x << " ";
        cout << "\n";
        return;
    }
    for (int x = 1; x <= n; x++) {
        if (iskoriscen[x]) continue;
        iskoriscen[x] = true; perm.push_back(x);    // izaberi
        generisi();                                  // istraži
        iskoriscen[x] = false; perm.pop_back();     // poništi
    }
}

int main() {
    cin >> n;
    iskoriscen.assign(n + 1, false);
    generisi();
    return 0;
}

Permutacije izlaze u leksikografskom poretku, jer se na svaku poziciju brojevi probaju od najmanjeg.

Permutacije pomoću next_permutation

U C++-u funkcija next_permutation (zaglavlje <algorithm>) pretvara niz u sledeću permutaciju u leksikografskom poretku i vraća false kada je stigla do poslednje. Niz mora na početku biti sortiran. Ako u nizu ima jednakih elemenata, svaka različita permutacija dobija se tačno jednom.

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

int main() {
    string s;
    cin >> s;
    sort(s.begin(), s.end());                     // počinjemo od najmanje permutacije
    int broj = 0;
    do {
        cout << s << "\n";
        broj++;
    } while (next_permutation(s.begin(), s.end()));
    cout << "Ukupno: " << broj << endl;
    return 0;
}

Kombinacije k od n

Kod kombinacija redosled nije bitan, pa da ne bismo dobili isti izbor dva puta, brojeve biramo rastuće: posle broja x sledeći biramo od x + 1.

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

int n, k;
vector<int> izbor;

void kombinacije(int od) {
    if ((int)izbor.size() == k) {
        for (int x : izbor) cout << x << " ";
        cout << "\n";
        return;
    }
    // odsecanje: ostalo je dovoljno brojeva da se izbor popuni
    for (int x = od; x <= n - (k - (int)izbor.size()) + 1; x++) {
        izbor.push_back(x);
        kombinacije(x + 1);
        izbor.pop_back();
    }
}

int main() {
    cin >> n >> k;
    kombinacije(1);
    return 0;
}

Podskupovi pomoću bitova

Podskup skupa od n elemenata može se predstaviti brojem od 0 do 2n − 1: ako je i-ti bit jedinica, element i je u podskupu. Ovo je kraće od rekurzije i dovoljno brzo za n ≤ 20.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    for (int maska = 0; maska < (1 << n); maska++) {
        cout << "{ ";
        for (int i = 0; i < n; i++)
            if (maska & (1 << i))                 // da li je i-ti bit jedinica
                cout << i + 1 << " ";
        cout << "}\n";
    }
    return 0;
}

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje