Generarea permutărilor

        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.