Generarea permutarilor

Se dă o mulţime cu n elemente A={a1,a2,…,an}. Se cere să se genereze si să se afişeze toate permutările ei. Altfel spus, se cere să se afişeze toate modurile în care se pot amesteca elementele mulţimii A.

Folosim pentru generare mulţimea {1,2,…,n}. Condiţiile care se pun sunt următoarele:

• • Fiecare element din vectorul X se ia din {1,2,…,n};

  • Un element Xk este valid dacă el nu a fost plasat anterior în vectorul soluţie X;

  • Când am generat n elemente cu condiţiile de mai sus, atunci avem o soluţie.

Se pot identifica mai multe modalităţi de a verifica dacă elementul Xk a fost plasat deja în vectorul soluţie. Cele mai importante două sunt:

• • parcurgerea elementelor deja generate pentru a verifica daca Xk apare sau nu între ele;

  • folosirea unui vector cu n elemente în care vom avea valori 0 sau 1 corespunzătoare elementelor mulţimii iniţiale. Valoarea 1 va preciza faptul că elementul de pe poziţia corespunzătoare a fost plasat anterior în vectorul soluţie, iar valoarea 0 că nu.

Corespunzător acestor două moduri de a verifica dacă un element a mai fost sau nu plasat în vectorul soluţie, avem 2 moduri de generare a permutărilor.

ENUNT: Fie n numar natural nenul (n<30). Scrieti un program de generare a permutarilor de ordin n a elementelor multimii {1, 2, 3,..., n}.

EXEMPLU: Pentru n=3 programul va genera

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

SOLUTIE: Permutarile de ordin n reprezinta toate posibilitatile de a aranja elementele unei multimi de n elemente.

• Solutia x[1]......x[n] - x[i] va avea ca valoare un element al multimii

• x[k] poate avea ca valoare orice valoare din intervalul [1,n]

• Valid - elementele trebuie sa fie distincte-> x[k] trebuie sa fie diferit de x[1]...x[k-1]

PROGRAM C++:

#include <iostream>

using namespace std;

char sp1[]=" ";

int x1[10], n1, nrsol1=0;

void Afisare()

{ int i;

cout<<sp1;

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

cout<<x1[i]<<" ";

cout<<endl;

nrsol1++;

}

int Valid(int k)

{ int i;

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

if (x1[k]==x1[i]) return 0;

return 1;

}

void BackRec1(int k)

{ int i;

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

{ x1[k]=i;

if (Valid(k))

if (k==n1) Afisare();

else BackRec1(k+1);

}

}

int main()

{ cout<<endl<<endl<<sp1<<"Permutarile primelor n numere naturale (n<10)"<<endl;

cout<<endl<<sp1<<" Dati valoarea lui n: "; cin>>n1;

cout<<endl;

BackRec1(1);

cout<<endl<<sp1<<"Numar solutii: "<<nrsol1;

return 0;

}