全排列
搜索实现
#include <iostream> #include <memory.h> using namespace std; int a[10001]; int b[10001]; int vis[10001]; int n; int sum=0; void dfs(int s){ if(s==n+1){ for(int i=1;i<=n;i++) cout<<b[i]<<" "; cout<<endl; sum++; return ; } for(int i=1;i<=n;i++){ if(!vis[i]){ b[s]=i; vis[i]=1; dfs(s+1); vis[i]=0; } } } int main() { memset(vis,0,sizeof(vis)); cin>>n; for(int i=1;i<=n;i++) a[i]=i; dfs(1); cout<<sum; return 0; } 去重全排列这是计蒜客2018蓝桥杯B组模拟题中代码填空的一个题目
我觉得搞懂这个算法很重要所以就写一下完整的代码
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N=1e3; char str[N], buf[N];//buffer int vis[N], total, len; void arrange(int num) { if (num == len){ printf("%s\n", buf); total++; return; } for (int i = 0; i < len; ++i) { if (!vis[i]) { int j; for (j = i + 1; j < len; ++j) { if (vis[j] && str[i]==str[j]) { break; } } if (j == len) { vis[i] = 1; buf[num] = str[i]; arrange(num + 1); vis[i] = 0; } } } } int main() { while (~scanf("%s",str)) { len = strlen(str); sort(str, str + len); total = 0; buf[len] = '\0'; arrange(0); printf("Total %d\n", total); } return 0; }如果用C++的STL中的next_permutation方法可以自动生成下一个全排列并且是去重的
#include <iostream> #include <algorithm> using namespace std; int a[10001]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) a[i]=i; int sum=0; do{ for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; sum++; }while(next_permutation(a+1,a+n+1)); cout<<sum; return 0; }