everything about permuations

there are two ways to do permutation.

1. recursive way

So the algorithm is:

1. Keep the first letter constant and do all the permutations of the second and third letters (printing out the entire string each time).
2. Swap the original first and second letters of the string, and repeat step 1 for the new string.
3. Swap the original first and third letters of the string, and repeat step 1 for the new string.

void perm(int *a, int ai, int len)
{
int i;

if(len == 0) {
for(int i=0;i<ai;i++)
cout<<a[i];
cout<<endl;
return;
}

for(i=0; i<len; i++) {
int temp=a[ai];
a[ai]=a[ai+i];
a[ai+i]=temp;
//swap(a, ai, ai+i);
perm(a, ai+1, len-1);
temp=a[ai];
a[ai]=a[ai+i];
a[ai+i]=temp;
//swap(a, ai, ai+i);

}
}

a special permutation that prevents all consecutive digits:

void special_perm(int *a, int ai, int len)

{

int i;

if(len == 0) {

for(int i=0;i<ai;i++)

cout<<a[i];

cout<<endl;

return;

}

for(i=0; i<len; i++) {

//if(ai == 0 || a[ai-1] +1 != a[ai+i]) {

int temp=a[ai];

a[ai]=a[ai+i];

a[ai+i]=temp;

//swap(a, ai, ai+i);

special_perm(a, ai+1, len-1);

temp=a[ai];

a[ai]=a[ai+i];

a[ai+i]=temp;

//swap(a, ai, ai+i);

//}

}

}

2. non recursive way:

void output_permutation(int n)

{

vector<int> cur_num(n);

for(int i=0;i<n;i++)

cur_num[i]=i+1;

while(true)

{

for(int i=0;i<n;i++)

cout<<cur_num[i];

cout<<endl;

vector<int> prev_num=cur_num;

int i,temp;

for(i=n-1;i>=0;i--)

{

int j;

for(j=n-1;j>i;j--)

if(prev_num[j]>prev_num[i])

{

temp=prev_num[j];

break;

}

if(j>i)

break;

}

if(i==-1)

break;

for(int j=0;j<i;j++)

cur_num[j]=prev_num[j];

int temp2=cur_num[i];

cur_num[i]=temp;

for(int j=i+1;j<n;j++)

{

if(prev_num[n-(j-i)]==cur_num[i])

prev_num[n-(j-i)]=temp2;

cur_num[j]=prev_num[n-(j-i)];

}

}

}