竞赛中关于排列问题可能会使用到next_permutation函数的一个全排列,但是仍然需要掌握基本的排列的递归写法,下面简单介绍一下用法。(直到如何使用即可)
1.STL中的next_permutation 用法
2.全排列的递归写法
1.使用STL里面的函数进行全排列:(全排列前要需要排序才行)
数字排序:
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
char a[] = {1,2,3};
sort(a,a+3);
do{
for(int i = 0;i < 3;i++) printf("%d ",a[]);
printf("\n");
}while(next_permutation(a,a+3));
return 0;
}
输出结果:
123
132
213
231
321
312
字符串全排列:
#include<stdio.h>
#include<algorithm>
using namespace std;
//int cmp(const void *a,const void *b){
// return *(char *)a-*(char *)b;
//}
int main(){
char a[] = "132";
sort(a,a+3);//C++
// qsort(a,3,sizeof(a[0]),cmp);//C
do{
printf("%s\n",a);
}while(next_permutation(a,a+3));
return 0;
}
输出结果:
123
132
213
231
321
312
结构体的全排序
解释一下,结构体没法全排列,所以可以借助下标进行全排列
#include<stdio.h>
#include<algorithm>
using namespace std;
const int Maxn = 3;
struct Node{
int x;
}a[100];
int q[100];
int main(){
for(int i = 1;i <= Maxn;i++){
a[i].x = q[i] = i; //让结构体元素按照正常顺全排列
// a[Maxn-i+1] = q[i] = i; //顺序将会相反
}
do{
for(int i = 1;i <= Maxn;i++) printf("%d ",a[q[i]].x);
printf("\n");
}while(next_permutation(q+1,q+Maxn+1));
return 0;
}
这个是STL中的源码可以参考一下,它的是非递归写法,下面会说到递归写法。参考链接
2.全排列的递归写法
#include <iostream>
using namespace std;
void get_permutation(char *a, int idx, int length) //左下标和长度值,从头循环到尾
{
if (idx == length-1){
for (int i=0; i<length; ++i)
printf("%s ",a);
printf("\n");
}
else {
for (int i=idx; i<length; ++i){
swap(a[i],a[idx]);
get_permutation(a,idx+1,length);
swap(a[i],a[idx]);
}
}
}
int main()
{
char array[] = "123";
get_permutation(array,0,3);
return 0;
}
输出结果:
123
132
213
231
321
312
简单用法就是上面局的例子,时间复杂度是在 O(n!) ~ O(n∗n!) 之间,还是比较花时间的,所以慎用(蓝桥杯中用法会比较多)
参考链接