PTA 输出全排列（20 分）

Kindear

发布于 2017-12-29 17:34:08

8710

发布于 2017-12-29 17:34:08

文章被收录于专栏：算法与数据结构算法与数据结构

7-2 输出全排列（20 分）

请编写程序输出前n个正整数的全排列（n<10），并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。

输入格式:

输入给出正整数n（<10）。

输出格式:

输出1到n的全排列。每种排列占一行，数字间无空格。排列的输出顺序为字典序，即序列a1,a2,⋯,an排在序列b1,b2,⋯,bn之前，如果存在k使得a1=b1,⋯,ak=bk 并且 ak+1<bk+1。

输入样例：

输出样例：

第一dfs

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int num[maxn];
void print_per(int n,int *A,int cur)
{
    if(cur==n)
    {
        for(int i=0;i<n;i++)
            printf("%d",A[i]);
        printf("\n");
    }
    else
    for(int i=1;i<=n;i++)
    {
        int ok = 1;
        for(int j=0;j<cur;j++)
        {
            if(A[j]==i) ok=0;
        }
        if(ok)
        {
            A[cur]=i;
            print_per(n,A,cur+1);
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        num[i] = i+1;
    print_per(n,num,0);
}

　　第二个就是比较骚了， C++stl 函数

#include <bits/stdc++.h>
using namespace std;
char getchars(int x)
{
    return (char)(x+'0');
}
int main()
{
    string s;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        s.push_back(getchars(i));
    cout<<s<<endl;
    while(next_permutation(s.begin(),s.end()))
    {
        cout<<s<<endl;
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-11-07 ，如有侵权请联系 cloudcommunity@tencent.com 删除

c++