Aranjamente

Se dau două mulţimi A={1,2,…,p} şi B={1,2,…,m} se cer toate funcţiile injective definite pe A cu valori în B. O astfel de problemă este una de generare a aranjamentelor de n luate cate p (Anp).

Exemplu: p=2, n=3. Avem (1,2), (2,1), (1,3), (3,1), (2,3), (3,2). De exemplu (2,1) este funcţia f:A→B dată astfel f(1)=2, f(2)=1. 

Se citesc m şi p. Să se genereze toate aranjamentele de m luate câte p.

Se observă că dacă se cunoaşte fiecare submulţime de p elemente a mulţimii de m elemente, atunci aranjamentele se pot obţine permutând în toate modurile posibile elementele unei astfel de mulţimi.

O soluţie este de forma: x1,x2,...xp  unde x1,x2,...xpÎB. În plus x1,x2,...xp trebuie să fie distincte. O soluţie are p numere din mulţimea B şi numerele trebuie să fie distincte.

De aici rezultă că algoritmul este acelaşi ca la permutări, diferenţa fiind dată de faptul că soluţia are p numere, nu m ca în cazul permutărilor. 

Exemplu:

#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(x[k]==x[i])    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;

  }

}