Metoda Backtaking



Enunt:Sa se genereze toate permutarile{1,2,…,n}.
Program permutari;
Uses crt;
Const max=25;
Type vector:array[1..25] of integer;
Var x:vector;
n:integer;
procedure citire;
begin
clrscr;
write(‘n=’);readln(n);
end;
procedure init(k:integer);
begin
x[k]:=0;
end;
function exista(k:integer):Boolean;
begin
exista:=(x[k]0 do
if exista(k) then
begin
x[k]:=x[k]+1;
if cont(k) then
if solutie(k) then
tipar(k);
else
begin
k:=k+1;
init(k);
end;
end;
else
k:=k-1;
end;
begin
citire;
bkt;
readln
end.

Algoritmul utilizat pentru generarea acestor combinari are in vedere faptul ca orice permutare este alcatuita din toate elementele multimii,care sunt distincte.
Pentru a scrie programul,stabilim urmatoarele repere:
Vectorul solutie are n componente:x[k]=v are semnificatia ca valoarea v este asezata pe pozitia k in combinatie;
Pentru orice k din {1,…,k-1} multimea valorilor posibile pentru x[k] este Ak={1,2,…,k-1};initializare se va face cu x[k]=0;
Conditia de continuare pentru ca o valoare x[k] sa fie acceptata trebuie ca pentru orice I apartine {1,2,…,k-1},x[k] diferit x[i](elementele nmultimii nu trebuie sa se repete);
Am gasit o solutie finala daca an completat toate componentele vectorului (deci k=n).
Pentru exemplul considerat,initial k=1,x[k]=0;(se incepe cu prima componenta si nu s-a testat nici o valoare ).Vectorul solutie se va completa astfel;
Stabilim prima valoare posibila pentru componenta k=1;aceasta convine si trecem la urmatoarea comoonenta ;k=2.
Stabilim prima valoare posubila pemtru componenta;k=2,x[2]=1;
Conditiile de continuare nu sunt indeplinite, deoarece valoare 1 mai apare in aceasta combinatie.De aceea ramanem la k=2.
Testam urmatoarea valoarea posibila pentru x[2],care este 2 –convine si se trece la urmatoarea componenta,k=3.
Incepem cu prima valoare posibila pentru aceasta componenta,x[3]=1;nu
Convine,deci ramanem la k=3.
Urmatoarea valoare posibila pentru x[k] este 2 si din nounu convine.
Valoarea x[3]=3 corespunde