2017-12-05 Generació combinatòria

p1.cc

// Genera totes les combinacions de vectors de n booleans.

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


void escriu(const vector<bool>& v) {
    for (bool b : v) cout << b;
    cout << endl;
}  


// Genera totes les combinacions del vector v deixant les 
// i primeres posicions fixades.
void genera(vector<bool>& v, int i) {
    int n = v.size();
    if (i == n) {
        escriu(v);
    } else {
        v[i] = false;
        genera(v, i + 1);
        v[i] = true;
        genera(v, i + 1);
    }
}


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

    vector<bool> v(n);
    genera(v, 0);
}

p2.cc

// Genera totes els subconjunts de n paraules donades.

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


void escriu(const vector<string>& w, const vector<bool>& v) {
    int n = v.size();
    for (int i = 0; i < n; ++i) {
        if (v[i]) {
            cout << w[i] << " ";
        }
    }
    cout << endl;
}  


// Genera totes les combinacions del vector v deixant les 
// i primeres posicions fixades.
void genera(const vector<string>& w, vector<bool>& v, int i) {
    int n = v.size();
    if (i == n) {
        escriu(w, v);
    } else {
        v[i] = false;
        genera(w, v, i + 1);
        v[i] = true;
        genera(w, v, i + 1);
    }
}


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

    vector<string> w(n);
    for (int i = 0; i < n; ++i) cin >> w[i];

    vector<bool> v(n);
    genera(w, v, 0);
}

p3.cc

// Genera totes les permutacions dels n primers naturals.

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


void escriu(const vector<int>& p) {
    for (int i : p) cout << i;
    cout << endl;
}  


// Genera totes les permutacions del vector v deixant les 
// i primeres posicions fixades sabent que el vector u 
// descriu els elements que ja s'han usat a les primeres i posicions.
void genera(vector<int>& p, vector<bool>& u, int i) {
    int n = p.size();
    if (i == n) {
        escriu(p);
    } else {
        for (int j = 0; j < n; ++j) {
            if (not u[j]) {
                p[i] = j;
                u[j] = true;
                genera(p, u, i + 1);
                u[j] = false;
            }
        } 
    }
}


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

    vector<int> p(n);
    vector<bool> u(n, false);
    genera(p, u, 0);
}

p4.cc

// Genera totes les permutacions de n paraules donades.

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


void escriu(const vector<string>& w, const vector<int>& p) {
    int n = p.size();
    for (int i = 0; i < n; ++i) {
        cout << w[p[i]] << " ";
    }
    cout << endl;
}  


// Genera totes les permutacions del vector v deixant les 
// i primeres posicions fixades sabent que el vector u 
// descriu els elements que ja s'han usat a les primeres i posicions.
void genera(const vector<string>& w, vector<int>& p, vector<bool>& u, int i) {
    int n = p.size();
    if (i == n) {
        escriu(w, p);
    } else {
        for (int j = 0; j < n; ++j) {
            if (not u[j]) {
                p[i] = j;
                u[j] = true;
                genera(w, p, u, i + 1);
                u[j] = false;
            }
        } 
    }
}


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

    vector<string> w(n);
    for (int i = 0; i < n; ++i) cin >> w[i];

    vector<int> p(n);
    vector<bool> u(n, false);
    genera(w, p, u, 0);
}