# In depth full permutation algorithm and its implementation method

• 2020-04-01 23:43:41
• OfStack

Full permutation is applied in many programs and is a very common algorithm. The conventional algorithm is a recursive algorithm, which is based on the following analysis ideas.  Given a set of n elements (n) > =1), which requires the output of all possible permutations of the elements in the set.
One, recursive implementation
For example, if the collection is {a, b, c}, so all the arrangement of elements in this collection is {(a, b, c), (a, c, b), (a, b, c), (b, c, a), (c, a, b), (c, b, a)}, obviously, for a given n elements with a total of n! If a given set is {a,b,c,d}, all permutations can be generated by the simple algorithm given below, that is, all permutations of set (a,b,c,d) are composed of the following permutations:
(1) the arrangement starting with a followed by (b,c,d)
(2) the arrangement starting with b followed by (a,c,d)
(3) the arrangement starting with c followed by (a,b,d)
(4) the arrangement starting with d followed by (a,b,c) is obviously a recursive idea, so we get the following implementation:
``````
#include "iostream"
using namespace std;
void permutation(char* a,int k,int m)
{
int i,j;
if(k == m)
{
for(i=0;i<=m;i++)
cout<<a[i];
cout<<endl;
}
else
{
for(j=k;j<=m;j++)
{
swap(a[j],a[k]);
permutation(a,k+1,m);
swap(a[j],a[k]);
}
}
}
int main(void)
{
char a[] = "abc";
cout<<a<<" The results of all permutations are: "<<endl;
permutation(a,0,2);
system("pause");
return 0;
}
``````

Ii. STL implementation
Sometimes the efficiency of recursion forces us to consider other implementations, and many of these algorithms are difficult to convert to non-recursive forms. At this point, let's not forget the algorithms that the standard template library has implemented, which makes it very easy. The STL has a function next_permutation() that returns true and produces the permutation(false) if there is a next permutation of this sort sorted by dictionary for a sequence. Note that in order to produce a full permutation, the sequence must be ordered, which means that sort is called once. The implementation is simple, let's take a look at the code:
``````
#include "iostream"
#include "algorithm"
using namespace std;
void permutation(char* str,int length)
{
sort(str,str+length);
do
{
for(int i=0;i<length;i++)
cout<<str[i];
cout<<endl;
}while(next_permutation(str,str+length));
}
int main(void)
{
char str[] = "acb";
cout<<str<<" The results of all permutations are: "<<endl;
permutation(str,3);
system("pause");
return 0;
}
``````

The full arrangement with certain constraints
The logarithms 1,2,3,4,5 have to be fully sorted. We want 4 to be to the left of 3, and we want everything else to be arbitrary.
Train of thought: first, use one of the two methods above to realize the full permutation, and then filter the full permutation to screen the 4 to the left of 3.
``````
#include "iostream"
#include "algorithm"
using namespace std;
void permutation(int* a,int length)
{
int i,flag;
sort(a,a+length);
do
{
for(i=0;i<length;i++)
{
if(a[i]==3)
flag=1;
else if(a[i]==4)             //If the 3 is to the left of the 4, and the code is executed, the flag is 2
flag=2;
}
if(flag==1)          //If the 4 is to the left of the 3, and the code is executed, the flag is 1
{
for(i=0;i<length;i++)
cout<<a[i];
cout<<endl;
}
}while(next_permutation(a,a+length));
}
int main(void)
{
int i,a[5];
for(i=0;i<5;i++)
a[i]=i+1;
printf("%d All within 4 in 3 The result of the full array on the left is: n",i);
permutation(a,5);
system("pause");
return 0;
}
``````

Related articles: