Generarea permutarilor. Se citeste un numar natural n. Sa se genereze toate permutarile multimii {1, 2, 3, …,n}.
Generarea permutarilor se va face tinand cont ca orice permutare va fi alcatuita din elemente distincte ale multimii A. Din acest motiv, la generarea unei permutari, vom urmari ca numerele sa fie distincte.
Prezentam algoritmul corespunzator cazului n=3:
|
|
|
|
|
|
|
1 |
|
2 |
|
3 |
|
|
|
1 |
|
2 |
|
2 |
|
2 |
|
2 |
1 |
|
1 |
|
1 |
|
1 |
|
1 |
|
1 |
|
|
|
1 |
|
2 |
|
3 |
|
|
|
|
3 |
|
3 |
|
3 |
|
3 |
|
|
|
1 |
1 |
|
1 |
|
1 |
|
1 |
|
2 |
|
2 |
1 |
|
2 |
|
3 |
|
|
|
|
|
1 |
1 |
|
1 |
|
1 |
|
2 |
|
3 |
|
3 |
2 |
|
2 |
|
2 |
|
2 |
|
2 |
|
2 |
se incarca in stiva pe nivelul 1 valoarea 1;
incarcarea valorii 1 pe nivelul al 2-lea nu este posibila, intrucat aceasta valoare se gaseste si pe nivelul 1 al stivei;
incarcarea valorii 2 pe nivelul al 2-lea este posibila, deoarece aceasta valoare nu mai este intalnita;
valoarea 1 din nivelul al 3-lea se regaseste pe nivelul 1;
valoarea 2 din nivelul al 3-lea se regaseste pe nivelul al 2-lea;
valoarea 3 pe nivelul al 3-lea nu e intalnita pe nivelurile anterioare; intrucat nivelul 3 este completat corect. Tiparim: 1 2 3
……
Algoritmul continua pana cand stiva devine vida.
Problema celor n dame. Fiind data o tabla de sah n´n se cer toate solutiile de aranjare a n dame, astfel incat sa nu se afle doua dame pe aceeasi linie, coloana sau diagonala (damele sa nu se atace reciproc).
Exemplu: Presupunand ca dispunem de o tabla de dimensiune 4´4, o solutie ar fi urmatoarea:
Cum procedam? Observam ca o dama trebuie sa fie plasata singura pe linie. Plasam prima dama pe linia 1 coloana 1.
A doua dama nu poate fi asezata decat pe coloana a 3-a.
