Generarea combinărilor

Citiți mai întâi Generarea aranjamentelor!

Introducere

Consideram o mulțime cu A cu n elemente. Prin combinări de k elemente din A înțelegem submulțimile cu k elemente ale multimii A. Numărul acestor combinări este \(C_n^k = \frac{A_n^k}{P_k}\). Mai multe formule pentru calculul numărului de combinări pot fi găsite în acest articol.

Acest articol prezintă un algoritm backtracking pentru determinarea în ordine lexicografică a combinărilor de k elemente ale mulțimii A={1 , 2 , ... , n}, elemente dintr-o combinare fiind generate în ordine crescătoare. El poate fi adaptat pentru determinarea combinărilor de k elemente ale unei mulțimi oarecare de n elemente.

Deoarece în algoritmul recursiv general apare funcția Back() cu parametrul k, pentru a păstra notațiile din algoritm vom considera în continuare combinările de k elemente luate câte p.

Soluția 1

Condiții

Ca orice rezolvare cu algoritmul backtracking, începem prin a preciza semnificația vectorului soluție. Astfel, x[] reprezintă o combinare. În consecință, el va respecta următoarele condiții:

elemenele vectorului sunt valori între 1 și n;
elementele nu se repetă;
elementele sunt ordonate crescător
vectorul se completează element cu element. Când va avea p elemente, reprezintă o combinare completă, care urmează a fi afișată.

Formal, exprimăm proprietățile de mai sus astfel:

condiții externe: \( x[k] \in \left\{ 1,2, \ldots, n \right\} \);
condiții interne:
- \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \ldots, x[ k-1 ] \right\}\), pentru \( k \in \left\{2,3, \ldots, n \right \} \)
- \(x[k] > x[k-1]\), pentru \( k \in \left\{2,3, \ldots, n \right \} \)
condiții de existență a soluției: \(k = p\)

Observăm (din nou) că în verificarea condițiilor interne intervine doar elementul x[k] (cel care este verificat) și elementele deja generate (x[1], x[2], … , x[k-1]).

Observăm că aceste condiții sunt cele de la generarea aranjamentelor, la care se adaugă condiția internă legată de ordinea elementelor din vector. În consecință, programul va fi cel de la aranjamente, cu completarea funcției OK().

Sursa C++

#include <iostream>
using namespace std;

int x[10] , n , p;

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

bool OK(int k){
    for(int i = 1 ; i < k ; ++ i)
        if(x[k] == x[i])
            return false;
    if(k > 1)
		if(x[k] <= x[k-1])
			return false;
    return true;
}

bool Solutie(int k)
{
    return k == p;
}

void back(int k){
    for(int i = 1 ; i <= n ; ++ i)
    {
        x[k] = i;
        if(OK(k))
            if(Solutie(k))
                Afis(k);
            else
                back(k + 1);
    }
}
int main(){
    cin >> n >> p;
    back(1);
    return 0;
}

Soluția 2

Rafinarea condițiilor

Condițiile de mai sus pot fi îmbunătățite, făcând următoarele observații:

cele două condiții interne pot fi reduse la una singură. Dacă pentru fiecare \( k \) are loc relația \(x[k] > x[k-1]\) atunci are loc și condiția \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \ldots, x[ k-1 ] \right\}\);
Condițiile devin:
- condiții externe: \( x[k] \in \left\{ 1,2, \ldots, n \right\} \);
- condiții interne: \(x[k] > x[k-1]\), pentru \( k > 1 \)
- condiții de existență a soluției: \(k = p\)
condiția internă poate fi transformată în condiție externă. Dacă \(x[k] > x[k-1]\) atunci valorile pe care le poate lua \(x[k]\) (condiții externe) sunt \( \left\{ x[k-1] + 1, \ldots, n \right\} \). Condițiile devin:
- condiții externe: \( x[k] \in \left\{ x[k-1] +1 , x[k-1] +2, \ldots, n \right\} \);
- condiții interne: nu există
- condiții de existență a soluției: \(k = p\)

Cazul \(k = 1\) este unul special. Valorile pe care le poate lua sunt \(\left\{ 1 , 2 , 3 , \ldots \right\} \). Pentru a fi condițiile externe de mai sus corecte în în acest caz, este necesară inițializarea x[ 0 ] = 0, înaintea începerii generării.

Sursă C++

#include <iostream>
using namespace std;

int x[10] , n , p;

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

void back(int k){
    for(int i = x[k-1] + 1 ; i <= n ; ++ i)
    {
        x[k] = i;
		if(k == p)
			Afis(k);
		else
			back(k + 1);
    }
}
int main(){
    cin >> n >> p;
    x[0] = 0;
    back(1);
    return 0;
}

Probleme

combinari combinari2 siruri SubmDiv cifre_c subimp2

Citește și

Generarea submulțimilor