全排列的两种解法（dfs和STL）

2019-11-11 05:10:23

字体：大中小

来源：转载

供稿：网友

首先写简单的那种、用STL模板里有一个神奇的函数叫做next_permutation(a,a+n)返回值为bool型，用来判断还有没有排列。记住先是字典序，才能用它产生去全排列。转自http://blog.sina.com.cn/s/blog_60bf5fda0101dufm.html http://acm.swust.edu.cn/oj/PRoblem/140/ code：

#include#includeusing namespace std;char str[15];int main(){ int n,i,j; while(scanf("%d",&n)!=EOF) { for(i=0;i str[i]=i+'1'; str[n]='/0'; do { printf("%s/n",str); }while(next_permutation(str,str+n)); } return 0;}

第二种方法就是dfs：

#include#includeusing namespace std;int str[15];//保存输出的字母表int visit[15];//标记是否读过int n;void dfs(int depth)//深度、也就是每次dfs增加一个数字、直到N个数字的时候输出{ int i,j; for(i=1;i<=n;i++)//遍历N个数字 { if(visit[i]==0)//如果没有读过此数字、则将这个数字放进输出表中、 { str[depth]=i; visit[i]=1;//标记为已打印 if(depth dfs(depth+1); else//满足题意、已经得到N个数，则打印出来 { for(j=1;j<=n;j++) printf("%d",str[j]); printf("/n"); } visit[i]=0;//如果已经打印一行之后、把以前的重新标记为未读 } }}int main(){ int i,j; scanf("%d",&n); memset(visit,0,sizeof(visit)); dfs(1); return 0;}

怎么说了、这个代码还是很好理解的、假设N=3 那么第一次循环、123、没有问题当运行打印的之后、将3标记为未读、则为13、再往前回溯、得到2、则输出132 继续往前回溯、for循环已经过了一遍、所以开头为2、所以是213 同理就是231 同理就是 312 321 仔细想一下就是这样了

上一篇：深入.NET平台和C#编程第一章概念+上机

下一篇：第19天(就业班) BeanUtils组件用法及类型转换器、DbUtils组件、jdbc优化