PERMUTARI ITERATIV

PERMUTARI ITERATIV metoda backtarcking

PERMUTĂRI. Se citeşte un număr natural n. Să se genereze permutările mulţimi {1, 2, …, n}

 

#include<iostream.h>
#include<conio.h>
#include<math.h>
int st[20],n,k,p;

void init()
{st[k]=0;}

int succesor()
{if (st[k]<n)
{st[k]++;
return 1;
}
else return 0;}

int valid()
{for(int i=1;i<k;i++)
if(st[i]==st[k]) return 0;
return 1;}

int sol()
{return (k==n);}

void tipar()
{for(int i=1;i<=n;i++) cout<<st[i];
cout<<endl;
}

void bkt()
{int as;
k=1;
init();
while(k>0)
{
do {} while ((as=succesor()) && !valid());
if (as)
if (sol()) tipar();
else {k++;init();}
else k–;
}
}

void main()
{
cout<<“n=”;cin>>n;
bkt();
}

 

permutari

//permutari
#include<iostream.h>
int st[20],n;

void init()
{
int i;
cout<<“n=”;cin>>n;
for(i=1;i<=n;i++) st[i]=0;
}

void tipar(int p)
{
int j;
for(j=1;j<=p;j++)
cout<<st[j]<<” “;
cout<<endl;
}

int valid(int p)
{
int i,ok;
ok=1;
for(i=1;i<p;i++)
if(st[p]==st[i]) ok=0;
return ok;
}

int solutie(int p)
{
return (p==n);
}

void bkt(int p)
{
int val;
for (val=1;val<=n;val++)
{
st[p]=val;
if (valid(p))
if(solutie(p))
tipar(p);
else
bkt(p+1);
}
}

void main()
{
init();
bkt(1);
}

{joscommentenable}