Aranjamente, combinări și submulțimi în C++

Aranjamentele aleg k elemente distincte și țin cont de ordine. Combinările aleg k elemente distincte fără să țină cont de ordine. Submulțimile permit și mărimi diferite. Diferența schimbă atât numărul rezultatelor, cât și condițiile din backtracking.

Pentru mulțimea {1,2,3}, alegerile (1,2) și (2,1) sunt aranjamente diferite, dar reprezintă aceeași combinare. Nu este suficient să generezi permutări și să elimini apoi duplicatele: poți construi direct fiecare rezultat o singură dată.

Cum funcționează

Pentru aranjamente păstrezi mecanismul de valori folosite de la permutări, însă te oprești după k poziții. Numărul rezultatelor este n!/(n-k)!. Pentru combinări, impui ca valorile alese să fie strict crescătoare. După v, următorul candidat începe de la v+1; ordinea crescătoare este reprezentantul unic al acelei selecții.

Programul implementează combinările pentru 0 <= k <= n <= 18. Parametrul first arată cea mai mică valoare disponibilă. Mai avem nevoie de k-pos elemente, deci nu are sens să începem atât de târziu încât să nu mai încapă suficiente valori până la n. Limita n-(k-pos)+1 taie exact aceste ramuri imposibile.

Pentru toate submulțimile, o altă reprezentare folosește n decizii binare: includem sau nu fiecare element. Sunt 2^n configurații, inclusiv submulțimea vidă și mulțimea întreagă. Poți folosi recursie sau măști de biți, dar limita n trebuie să fie compatibilă cu lățimea măștii și cu volumul rezultatelor. Generarea pe mărimi prin combinări este o a treia variantă corectă.

Exemplu urmărit pas cu pas

Pentru n=4 și k=2, prima valoare este 1 și poate fi urmată de 2,3,4. Apoi prima valoare devine 2 și poate fi urmată de 3,4. Ultima alegere inițială utilă este 3, urmată de 4. Obținem 12,13,14,23,24,34.

Nu afișăm 21, deoarece ar încălca ordinea strict crescătoare și ar reprezenta aceeași mulțime ca 12. Pentru k=0 există o singură combinare, cea vidă; programul o reprezintă printr-o linie goală. Acesta este un rezultat, nu absența rezultatelor.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int n, k, x[20];
void back(int pos, int first) {
    if (pos == k) {
        for (int i = 0; i < k; ++i)
            std::cout << x[i] << (i + 1 == k ? '\n' : ' ');
        if (k == 0)
            std::cout << '\n';
        return;
    }
    for (int v = first; v <= n - (k - pos) + 1; ++v) {
        x[pos] = v;
        back(pos + 1, v + 1);
    }
}
int main() {
    std::cin >> n >> k;
    back(0, 1);
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int n, k;
std::vector<int> x(20);
void back(int pos, int first) {
    if (pos == k) {
        for (int i = 0; i < k; ++i)
            std::cout << x[i] << (i + 1 == k ? '\n' : ' ');
        if (k == 0)
            std::cout << '\n';
        return;
    }
    for (int v = first; v <= n - (k - pos) + 1; ++v) {
        x[pos] = v;
        back(pos + 1, v + 1);
    }
}
int main() {
    std::cin >> n >> k;
    back(0, 1);
}

Generarea aranjamentelor și a tuturor submulțimilor

Pentru aranjamente alegem pe rând k valori distincte din 1..n, fără condiția crescătoare. Marcajul used împiedică repetarea unei valori în același rezultat și este anulat la revenire. Limitele exemplului sunt 0 <= k <= n <= 8, tocmai fiindcă numărul rezultatelor crește rapid. Pentru k=0 afișăm o singură linie goală. Sunt A(n,k)=n!/(n-k)! rezultate, iar afișarea lor costă O(k·A(n,k)) pentru k pozitiv.

Pentru toate submulțimile, fiecare valoare primește două decizii: o omitem sau o includem. La capăt afișăm valorile incluse, în ordine crescătoare. Limita este 0 <= n <= 8; există 2^n rezultate, inclusiv mulțimea vidă, reprezentată prin linia goală. Timpul cu afișare este O(n·2^n), iar starea și stiva ocupă O(n). Capacitatea clasică zece este suficientă ambelor exemple; variantele vector folosesc aceiași indici și aceleași limite. Ordinea afișării diferă de ordinea după dimensiunea submulțimii, dar fiecare rezultat apare exact o dată.

Aranjamente

Varianta cu tablou clasic:

#include <iostream>
int n, k, x[10];
bool used[10] = {};
void back(int pos) {
    if (pos == k) {
        for (int i = 0; i < k; ++i)
            std::cout << x[i] << ' ';
        std::cout << '\n';
        return;
    }
    for (int v = 1; v <= n; ++v)
        if (!used[v]) {
            x[pos] = v;
            used[v] = true;
            back(pos + 1);
            used[v] = false;
        }
}
int main() {
    std::cin >> n >> k;
    back(0);
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int n, k;
std::vector<int> x(10);
std::vector<char> used(10, 0);
void back(int pos) {
    if (pos == k) {
        for (int i = 0; i < k; ++i)
            std::cout << x[i] << ' ';
        std::cout << '\n';
        return;
    }
    for (int v = 1; v <= n; ++v)
        if (!used[v]) {
            x[pos] = v;
            used[v] = true;
            back(pos + 1);
            used[v] = false;
        }
}
int main() {
    std::cin >> n >> k;
    back(0);
}

Submulțimi

Varianta cu tablou clasic:

#include <iostream>
int n, x[10];
void back(int value, int count) {
    if (value > n) {
        for (int i = 0; i < count; ++i)
            std::cout << x[i] << ' ';
        std::cout << '\n';
        return;
    }
    back(value + 1, count);
    x[count] = value;
    back(value + 1, count + 1);
}
int main() {
    std::cin >> n;
    back(1, 0);
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int n;
std::vector<int> x(10);
void back(int value, int count) {
    if (value > n) {
        for (int i = 0; i < count; ++i)
            std::cout << x[i] << ' ';
        std::cout << '\n';
        return;
    }
    back(value + 1, count);
    x[count] = value;
    back(value + 1, count + 1);
}
int main() {
    std::cin >> n;
    back(1, 0);
}

De ce funcționează și cât costă

Fiecare combinare poate fi ordonată crescător într-un singur mod. Algoritmul produce numai șiruri strict crescătoare și explorează fiecare alegere care lasă suficiente elemente. Astfel, niciun rezultat valid nu lipsește și niciunul nu este repetat.

Numărul combinărilor este C(n,k). Afișarea cere O(kC(n,k)) operații pentru k pozitiv. Memoria de lucru este O(k). Pentru submulțimi, afișarea explicită a elementelor poate costa O(n2^n).

Greșeli frecvente

Nu confunda absența ordinii în rezultat cu lipsa ordinii în reprezentare: ordonarea crescătoare este tocmai metoda de evitare a duplicatelor. Dacă intrarea conține valori repetate, trebuie decis dacă selectăm poziții sau valori distincte.

Exersează

Pentru n=4, compară numărul aranjamentelor de două elemente cu numărul combinărilor de două elemente.

Rezolvare explicată: Aranjamentele sunt 4*3=12. Combinările sunt șase, deoarece fiecare pereche neordonată apare în două ordini în lista aranjamentelor. Împărțirea la 2 este justificată de aceste două permutări.

Continuă să înveți

Backtracking, baze și biți și funcții recursive.

Întrebări frecvente

Cum disting aranjamentele de combinări?

Întreabă dacă schimbarea ordinii schimbă rezultatul. Dacă da, ai o situație de tip aranjament; dacă nu, o selecție de mărime fixă este o combinare.

De ce alegem valori crescătoare la combinări?

Aceeași selecție are o singură ordine strict crescătoare. Restricția evită generarea tuturor reordonărilor fără să elimine vreo combinare distinctă.

Câte submulțimi are o mulțime cu n elemente?

Are 2^n submulțimi, deoarece fiecare element are două stări independente: inclus sau exclus. Numărul include și submulțimea vidă.

Există o combinare cu zero elemente?

Da, există exact una: selecția vidă. Această convenție este importantă pentru formule și pentru cazul de bază al generatorului.

Ce fac dacă valorile de intrare se repetă?

Precizezi dacă elementele sunt identificate prin poziție sau prin valoare. Pentru rezultate distincte după valoare, generatorul trebuie să evite alegerile echivalente.