Generarea aranjamentelor

Generăm aranjamentele unei mulţimi atunci când ne se cer toate modurile de a alege m elemente distincte dintre cele n ale mulţimii (m<n).

Această problemă se rezolvă foarte uşor folosind metodele de generarea permutărilor. Singurele modificări presupun citirea numărului m, modificarea condiţiei de soluţie, care va fi k=m în loc de k=n şi a numărului de elemente afişate.

Definiţie: Fie A o mulţime cu n elemente. Aranjamentele de n elemente luate câte c sunt toate

submulţimile ordonate 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: - fiecare componentă apare o singură dată

Numărul aranjamentelor:

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. for(i=1;i<k;i++)

19. if(x[i]==x[k])return 0;

20. return 1;

21. }

22.

23. void back()

24. {

25. int i,k=1;

26. x[1]=0;

27. while(k>0)//stiva nu este vida

28. {

29. while(x[k]<n)

30. {

31. x[k]=x[k]+1;

32. if(valid(k))

33. if(k==c) tipar();

34. else{k=k+1;x[k]=0;}

35. }

36. k=k-1;

37. }

38. }

39.

40. int main()

41. {

42. cin>>n;

43. cin>>c;

44. back();

45. cout<<nr;

46. }

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. for(i=1;i<k;i++)

19. if(x[i]==x[k])return 0;

20. return 1;

21. }

22.

23. void back(int k)

24. {

25. int i;

26. if(k==c+1)tipar();

27. else

28. for(i=1;i<=n;i++)

29. {

30. x[k]=i;

31. if(valid(k)) back(k+1);

32. }

33. }

34.

35. int main()

36. {

37. cin>>n;

38. cin>>c;

39. back(1);

40. cout<<nr;

41. }