全排列（深度优先，排列树）

 1)深度优先搜索

/**
    1)深度优先搜索
*/


#include <iostream>
#include <cstdio>
#include <ctime>
#include <algorithm>
using namespace std;
const int maxn=200;
int p[maxn],ans=0;
bool hashTable[maxn]={0};
void fullper(int x,int n);  //填充第x号位的数
int temp_max=0,temp_min=0;
int main()
{
    int n;
    printf("输入一个正整数:\n");
    scanf("%d",&n);
    clock_t start,stop;
    start=clock();
    fullper(1,n);
    cout << ans << endl;
    cout << temp_max << endl;
    cout << temp_min << endl;
    stop =clock();
    printf("运行时间 %.2f\n",(double)(stop-start)/CLK_TCK);
//    int b[]={4,2,3,7};
//    do
//    {
//        printf("%d %d %d %d\n",b[0],b[1],b[2],b[3]);
//    }while(next_permutation(b,b+4));
//    cout << "\nHello world!" << endl;
//    printf("%d %d %d %d\n",b[0],b[1],b[2],b[3]);
    return 0;
}

void fullper(int x,int n)
{
    if(x==n+1)
    {
        ++ans;
        for(int i=1;i<=n;i++)
        {
            printf("%d",p[i]);
            if(i<n) printf(" ");
        }
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        ++temp_max;
        if(hashTable[i]==0)
        {
            ++temp_min;
            p[x]=i;
            hashTable[i]=1;
            fullper(x+1,n);
            hashTable[i]=0;
        }
    }
}

2)排列树

/**
    2)排列树
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <ctime>
using namespace std;
const int maxn=200;
int p[maxn],ans=0;
bool hashTable[maxn]={0};
void fullper(int x,int n);
int temp=0;
int main()
{
    clock_t start,stop;
    int n;
    printf("输入一个正整数:\n");
    scanf("%d",&n);
    start=clock();
    for(int i=1;i<=n;++i)
        p[i]=i;
    fullper(1,n);
    cout << ans << endl;
    cout << temp << endl;
    stop =clock();
    printf("运行时间 %.2f\n",(double)(stop-start)/CLK_TCK);
//    int b[]={4,2,3,7};
//    do
//    {
//        printf("%d %d %d %d\n",b[0],b[1],b[2],b[3]);
//    }while(next_permutation(b,b+4));
//    cout << "\nHello world!" << endl;
//    printf("%d %d %d %d\n",b[0],b[1],b[2],b[3]);
    return 0;
}

void fullper(int x,int n)
{
    if(x==n+1)
    {
        ++ans;
        for(int i=1;i<=n;i++)
        {
            printf("%d",p[i]);
            if(i<n) printf(" ");
        }
        printf("\n");
        return;
    }
    for(int i=x;i<=n;i++)
    {
        ++temp;
        swap(p[i],p[x]);
        fullper(x+1,n);
        swap(p[i],p[x]);
    }
}