Lectie 7.2.2: Algoritmi rezolvati in C++ pentru Permutări, aranjamente, combinări și bactracking

Introducere

In aceasta lectie, vom explora algoritmi rezolvati in limbajul de programare C++ pentru problemele de permutări, aranjamente, combinări și bactracking. Aceste probleme sunt comune în domeniul informaticii și sunt utilizate în diverse aplicații, cum ar fi criptografia, optimizarea și inteligența artificială.

Permutări

O permutare este o aranjare a unui set de obiecte într-o ordine specifică. De exemplu, pentru un set de trei obiecte {A, B, C}, permutările posibile sunt ABC, ACB, BAC, BCA, CAB și CBA. Pentru a rezolva această problemă în C++, putem folosi algoritmul recursiv de backtracking.

Algoritmul de backtracking pentru permutări

Pentru a genera toate permutările unui set de obiecte, putem folosi un algoritm de backtracking. Algoritmul constă în a alege fiecare obiect într-o poziție specifică și apoi a genera toate permutările pentru obiectele rămase. Acest proces se repetă recursiv până când toate obiectele au fost plasate într-o poziție.

#include <iostream>
#include <vector>

using namespace std;

void backtracking_permutations(vector<int> &set, vector<int> &current_permutation, vector<bool> &used) {
    if (current_permutation.size() == set.size()) {
        for (int i = 0; i < current_permutation.size(); i++) {
            cout << current_permutation[i] << " ";
        }
        cout << endl;
    } else {
        for (int i = 0; i < set.size(); i++) {
            if (!used[i]) {
                used[i] = true;
                current_permutation.push_back(set[i]);
                backtracking_permutations(set, current_permutation, used);
                current_permutation.pop_back();
                used[i] = false;
            }
        }
    }
}

int main() {
    vector<int> set = {1, 2, 3};
    vector<int> current_permutation;
    vector<bool> used(set.size(), false);
    
    backtracking_permutations(set, current_permutation, used);
    
    return 0;
}

Aranjamente

Un aranjament este o permutare în care ordinea elementelor este importantă. De exemplu, pentru un set de trei obiecte {A, B, C}, aranjamentele posibile sunt ABC, ACB, BAC, BCA, CAB și CBA. Pentru a rezolva această problemă în C++, putem folosi, de asemenea, algoritmul de backtracking.

Algoritmul de backtracking pentru aranjamente

Pentru a genera toate aranjamentele unui set de obiecte, putem adapta algoritmul de backtracking folosit pentru permutări. Diferența constă în faptul că, în fiecare pas, trebuie să verificăm dacă obiectul curent a fost deja utilizat în aranjamentul parțial. Dacă a fost utilizat, trecem la următorul obiect disponibil.

#include <iostream>
#include <vector>

using namespace std;

void backtracking_arrangements(vector<int> &set, vector<int> &current_arrangement, vector<bool> &used) {
    if (current_arrangement.size() == set.size()) {
        for (int i = 0; i < current_arrangement.size(); i++) {
            cout << current_arrangement[i] << " ";
        }
        cout << endl;
    } else {
        for (int i = 0; i < set.size(); i++) {
            if (!used[i]) {
                used[i] = true;
                current_arrangement.push_back(set[i]);
                backtracking_arrangements(set, current_arrangement, used);
                current_arrangement.pop_back();
                used[i] = false;
            }
        }
    }
}

int main() {
    vector<int> set = {1, 2, 3};
    vector<int> current_arrangement;
    vector<bool> used(set.size(), false);
    
    backtracking_arrangements(set, current_arrangement, used);
    
    return 0;
}

Combinări

O combinație este o selecție de obiecte în care ordinea nu este importantă. De exemplu, pentru un set de trei obiecte {A, B, C}, combinațiile posibile sunt AB, AC și BC. Pentru a rezolva această problemă în C++, putem folosi o abordare recursivă similară cu cea utilizată pentru permutări și aranjamente.

Algoritmul recursiv pentru combinații

Pentru a genera toate combinațiile unui set de obiecte, putem folosi un algoritm recursiv. Algoritmul constă în a alege fiecare obiect într-o poziție specifică și apoi a genera toate combinațiile pentru obiectele rămase. Acest proces se repetă recursiv până când toate obiectele au fost selectate sau nu mai sunt obiecte disponibile.

#include <iostream>
#include <vector>

using namespace std;

void recursive_combinations(vector<int> &set, vector<int> &current_combination, int start_index) {
    for (int i = start_index; i < set.size(); i++) {
        current_combination.push_back(set[i]);
        
        for (int j = 0; j < current_combination.size(); j++) {
            cout << current_combination[j] << " ";
        }
        cout << endl;
        
        if (i < set.size() - 1) {
            recursive_combinations(set, current_combination, i + 1);
        }
        
        current_combination.pop_back();
    }
}

int main() {
    vector<int> set = {1, 2, 3};
    vector<int> current_combination;
    
    recursive_combinations(set, current_combination, 0);
    
    return 0;
}

Concluzie

În această lectie, am explorat algoritmi rezolvati in limbajul de programare C++ pentru problemele de permutări, aranjamente, combinări și bactracking. Aceste algoritmi sunt esențiali în rezolvarea diverselor probleme de optimizare și criptografie. Prin înțelegerea și aplicarea acestor algoritmi, programatorii pot dezvolta soluții eficiente și elegante pentru provocările lor.