Combinari

Fiind dată o mulţime A cu n elemente, a combina elementele mulţimii în grupe de câte p<n elemente înseamnă a determina toţi vectorii cu p elemente ale căror componente aparţin mulţimii A şi sunt sortate crescător.

Ne gândim la generarea combinărilor atunci când se dă o mulţime cu n elemente ca date de intrare iar soluţia este sub forma unui vector cu p<n elemente, astfel încât să nu aibă importanţă ordinea pe care o au în cadrul şirului. Componentele sunt sortate crescător şi aparţin mulţimii date.

Fie A={1,2,3}. Combinările mulţimii A în grupe de câte două elemente sunt (1,2), (1,3), (2,3).

#include<iostream.h>

#include<stdio.h>

typedef int sir[100];

sir x;

int i,k,m,p;

int as,ev;

sir a;

void succ(sir x, int k, int &as)

{

if(x[k]<m)

  {

  as=1;

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

  }

else as=0;

}

void valid(sir x, int k, int &as)

{

int i;

ev =1;

for(i=1;i<=k-1;i++)

if((k>=2)&&!(a[x[k]]>a[x[k-1]]))     ev=0;

}

void afis(sir x, int k)

{

int i;

for(i=1;i<=k;i++)

  cout<<a[x[i]]<<" ";  cout<<endl; 

}

int main(void)

{

cout<<"m=";

cin>>m;

for(i=1;i<=m;i++)

  cin>>a[i];

cout<<"p=";

cin>>p;

k=1;

x[k]=0;

while(k>0)

  {

  do

    {

  succ(x,k,as);

  if(as) valid(x,k,ev);

  }

  while(as&&!ev);

  if(as)

  if(k==p) afis(x,k);  else

  {

  k=k+1;

  x[k]=0;

  }

  else k=k-1;

  }

}