原题:P1706 全排列问题
这题显然可以暴力,长达164行:
#include<iostream>
#include<istream>
#include<ostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<utility>
#include<deque>
#include<ctime>
#include<sstream>
#include<list>
#include<bitset>
using namespace std;
int main(){
int n;
cin >> n;
if(n==1){
cout << " 1" << endl;
return 0;
}
if(n==2){
cout << " 1 2" << endl;
cout << " 2 1" << endl;
return 0;
}
if(n==3){
cout << " 1 2 3" << endl;
cout << " 1 3 2" << endl;
cout << " 2 1 3" << endl;
cout << " 2 3 1" << endl;
cout << " 3 1 2" << endl;
cout << " 3 2 1" << endl;
}
if(n==4){
for(int a=1;a<=n;a++){
for(int b=1;b<=n;b++){
for(int c=1;c<=n;c++){
for(int d=1;d<=n;d++){
if(a!=b && a!=c && a!=d && b!=c && b!=d && c!=d){
cout << " " << a << " " << b << " " << c << " " << d << endl;
}
}
}
}
}
return 0;
}
if(n==5){
for(int a=1;a<=n;a++){
for(int b=1;b<=n;b++){
for(int c=1;c<=n;c++){
for(int d=1;d<=n;d++){
for(int e=1;e<=n;e++){
if(a!=b && a!=c && a!=d && a!=e && b!=c && b!=d && b!=e && c!=d && c!=e && d!=e){
cout << " " << a << " " << b << " " << c << " " << d << " " << e << endl;
}
}
}
}
}
}
return 0;
}
if(n==6){
for(int a=1;a<=n;a++){
for(int b=1;b<=n;b++){
if(a!=b){
for(int c=1;c<=n;c++){
if(b!=c){
for(int d=1;d<=n;d++){
if(c!=d){
for(int e=1;e<=n;e++){
if(d!=e){
for(int f=1;f<=n;f++){
if(a!=b && a!=c && a!=d && a!=e && a!=f && b!=c && b!=d && b!=e && b!=f && c!=d && c!=e && c!=f && d!=e && d!=f && e!=f){
cout << " " << a << " " << b << " " << c << " " << d << " " << e << " " << f << endl;
}
}
}
}
}
}
}
}
}
}
}
return 0;
}
if(n==7){
for(int a=1;a<=n;a++){
for(int b=1;b<=n;b++){
if(a!=b){
for(int c=1;c<=n;c++){
if(b!=c){
for(int d=1;d<=n;d++){
if(c!=d){
for(int e=1;e<=n;e++){
if(d!=e){
for(int f=1;f<=n;f++){
if(e!=f){
for(int g=1;g<=n;g++){
if(a!=b && a!=c && a!=d && a!=e && a!=f && a!=g && b!=c && b!=d && b!=e && b!=f && b!=g && c!=d && c!=e && c!=f && c!=g && d!=e && d!=f && d!=g && e!=f && e!=g && f!=g){
cout << " " << a << " " << b << " " << c << " " << d << " " << e << " " << f << " " << g << endl;
}
}
}
}
}
}
}
}
}
}
}
}
}
return 0;
}
if(n==8){
for(int a=1;a<=n;a++){
for(int b=1;b<=n;b++){
if(a!=b){
for(int c=1;c<=n;c++){
if(b!=c){
for(int d=1;d<=n;d++){
if(c!=d){
for(int e=1;e<=n;e++){
if(d!=e){
for(int f=1;f<=n;f++){
if(e!=f){
for(int g=1;g<=n;g++){
if(f!=g){
for(int h=1;h<=n;h++){
if(a!=b && a!=c && a!=d && a!=e && a!=f && a!=g && b!=c && b!=d && b!=e && b!=f && b!=g && c!=d && c!=e && c!=f && c!=g && d!=e && d!=f && d!=g && e!=f && e!=g && f!=g && a!=h && b!=h && c!=h && d!=h && e!=h && f!=h && g!=h){
cout << " " << a << " " << b << " " << c << " " << d << " " << e << " " << f << " " << g << " " << h << endl;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
return 0;
}
}
但这只建立在n<=9的条件之上，而且代码也太长了，所以我们可以用#include<algorithm>里面的next_permutation函数来生成下一个全排列:代码长度降低到了18行!!!
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int num[15];
int main(){
int n;
cin>>n;
for(register int i=1;i<=n;++i)
num[i]=i;
do{
for(register int i=1;i<=n;++i){
printf("%5d",num[i]);
}
printf("\n");
}while(next_permutation(num+1,num+n+1));
return 0;
}
还可以用深度优先搜索(代码有注释欧).
#include<iostream>//istream ans ostream
using namespace std;//using namespace std;
int a[11];//来存全排列
int n;//n的全排列
int total;//全排列个数
int vis[11];//访问过?
void search(int step)//深度优先搜索
{
if(step==n+1)//如果填完了
{
for(int i=1;i<=n;i++)//输出排列
{
cout << " " << a[i];
}
total++;//总数+1
cout << endl;
}
else
{
for(int i=1;i<=n;i++)
{
if(vis[i]==0)//如果没有被访问
{
a[step]=i;//增加这个数
vis[i]=1;//标记为true
search(step+1);//search(step+1)
vis[i]=0;//回溯算法
}
}
}
}
int main()
{
cin >> n;//输入n
search(1);//dfs
return 0;
}
暴力: 空间:708.00KB 时间:94ms 代码长度:3.93KB
STL:空间:620.00KB 时间:51ms 代码长度:319B
DFS:空间:620.00KB 时间:78ms 代码长度:436B
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
