Generăm combinărilor unei mulţimi presupune o condiţie suplimentară faţă de permutări sau aranjamente. Acest lucru se datorează faptului că generarea combinărilor presupune alegerea în ordine strict crescătoare a elementelor care compun vectorul soluţie.
Astfel, condiţia de continuare, sau de validare a unui element este aceea că el trebuie să fie strict mai mare decât cel plasat anterior. În acest mod asigurăm faptul că elementele nu se vor repeta şi că vor fi generate în ordine strict crescătoare. Trebuie, însă, să avem grijă să nu punem această condiţie si asupra primului element din vectorul soluţie, deoarece el nu are cu cine să fie comparat.
O optimizare a algoritmului de generare a combinărilor se poate obţine pornind instrucţiunea for pentru plasarea unui element de la valoare următoare valorii generate anterior. Trebuie să avem grijă la prima poziţie, care nu are element anterior. Am putea iniţializa X0 cu 0. Astfel nu mai trebuie să verificăm dacă elementul Xk este mai mare ca Xk-1.
Definiţie: Fie A o mulţime cu n elemente. Combinările de n elemente luate câte c sunt toate
submulţimile ale lui A care au fiecare câte c elemente.
Reprezentarea soluţiei: - fiecare componentă are valori în mulţimea {1,2,….,n}
-soluţia are c componente
Condiţia de validare: - componentele unei soluţii sunt diferite (condiţia de la permutări)
- componentele unei soluţii le scriem în ordine crescătoare
Din cele două condiţii rămâne doar condiţia ca soluţia să aibă componentele în ordine crescătoare.
Pentru soluţia parţială (x1,x2,...,xk-1) avem x1 < x2 <...< xk-1 . Pentru a trece la soluţia următoare
(x1,x2,...,xk-1,xk) mai trebuie să verificăm doar condiţia: xk-1 < xk.
Numărul combinărilor:
Varianta iterativă
1. #include<iostream>
2. using namespace std;
3. int x[30];
4. int n,c,nr;
5.
6. void tipar()
7. {
8. int i;
9. for(i=1;i<=c;i++)
10. cout<<x[i]<<' ';
11. cout<<'\n';
12. nr++;
13. }
14.
15. int valid(int k)
16. {
17. int i;
18. if(x[k]>x[k-1])return 1;
19. return 0;
20. }
21.
22. void back()
23. {
24. int i,k=1;
25. x[1]=0;
26. while(k>0)//stiva nu este vida
27. {
28. while(x[k]<n)
29. {
30. x[k]=x[k]+1;
31. if(valid(k))
32. if(k==c) tipar();
33. else{k=k+1;x[k]=0;}
34. }
35. k=k-1;
36. }
37. }
38.
39. int main()
40. { x[0]=0; //valoarea iniţială
41. cin>>n;
42. cin>>c;
43. back();
44. cout<<nr;
45. }
Varianta recursivă
1. #include<iostream>
2. using namespace std;
3. int x[30];
4. int n,c,nr;
5.
6. void tipar()
7. {
8. int i;
9. for(i=1;i<=c;i++)
10. cout<<x[i]<<' ';
11. cout<<'\n';
12. nr++;
13. }
14.
15. int valid(int k)
16. {
17. int i;
18. if(x[k]>x[k-1])return 1;
19. return 0;
20. }
21.
22. void back(int k)
23. {
24. int i;
25. if(k==c+1)tipar();
26. else
27. for(i=1;i<=n;i++)
28. {
29. x[k]=i;
30. if(valid(k)) back(k+1);
31. }
32. }
33.
34. int main()
35. { x[0]=0; //valoarea iniţială
36. cin>>n;
37. cin>>c;
38. back(1);
39. cout<<nr;
40. }