算法笔记8.1小节搜索专题-深度优先搜索DFS问题-A-递归入门全排列

JAY.LIN 收录于算法笔记

2025-03-10 约 427 字预计阅读 1 分钟

https://bing.ee123.net/img/rand?artid=146158785

《算法笔记》8.1小节——搜索专题-＞深度优先搜索（DFS）问题 A: 【递归入门】全排列

题目描述

排列与组合是常用的数学方法。先给一个正整数 ( 1 < = n < = 10 )，例如n＝3，所有组合,并且按字典序输出：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

输入

输入一个整数n(1<=n<=10)

输出

输出所有全排列，每个全排列一行，相邻两个数用空格隔开（最后一个数后面没有空格。

样例输入

样例输出

题目链接：

分析：这道题实际上是第4章入门篇（2）——算法初步第3节第2目递归下的例子，当然在第4章也是用递归生成的。实际上用stl的next_permutation()也是可以的。

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include   <string>
#include   <vector>
#include   <cstdio>
#include    <queue>
#include    <stack>
#include    <ctime>
#include    <cmath>
#include      <map>
#include      <set>
#define ll long long
#define INF 0x3f3f3f3f
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,a) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<endl
using namespace std;

void getans(int n,int index,int *temp,int *flag)
{
    if(index==n)
    {
        for(int i=0;i<n;++i)
            i==0?printf("%d",temp[i]):printf(" %d",temp[i]);
        printf("\n");
    }
    for(int i=1;i<=n;++i)
    {
        if(flag[i]==0)
        {
            temp[index]=i;flag[i]=1;
            getans(n,index+1,temp,flag);
            flag[i]=0;
        }
    }

    return;
}

int main(void)
{
    #ifdef test
    freopen("in.txt","r",stdin);
//    freopen("in.txt","w",stdout);
    clock_t start=clock();
    #endif //test

    int n;
    while(~scanf("%d",&n))
    {
        int ans[n+5]={0},flag[n+5]={0};
        getans(n,0,ans,flag);
    }

    #ifdef test
    clockid_t end=clock();
    double endtime=(double)(end-start)/CLOCKS_PER_SEC;
    printf("\n\n\n\n\n");
    cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位
    cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位
    #endif //test
    return 0;
}