PTA 输出全排列

题目描述

请编写程序输出前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。

输入样例

3

输出样例

123

132

213

231

312

321

我们尝试用递归的思想解决：先输出所有以1开头的排列（这一步是递归调用），然后输出以2开头的排列（又是递归调用），接着是以3开头的排列……最后才是以n开头的排列。
以1开头的排列的特点是：第一位是1，后面是2～9的排列。根据字典序的定义，这些2～9的排列也必须按照字典序排列。换句话说，需要“按照字典序输出2～9的排列”，不过需注意的是，在输出时，每个排列的最前面要加上“1”。这样一来，所设计的递归函数需要以下参数：

已经确定的“前缀”序列，以便输出。
需要进行全排列的元素集合，以便依次选做第一个元素。

void print_permutation(序列A, 集合S)
{
    if(S为空) 输出序列A;
    else 按照从小到大的顺序依次考虑S的每个元素v
    {
        print_permutation(在A的末尾填加v后得到的新序列, S-{v});
    }
}

暂时不用考虑序列A和集合S如何表示，首先理解一下上面的伪代码。递归边界是S为空的情形，这很好理解：现在序列A就是一个完整的排列，直接输出即可。接下来按照从小到大的顺序考虑S中的每个元素，每次递归调用以A开头。下面考虑程序实现。不难想到用数组表示序列A，而集合S根本不用保存，因为它可以由序列A完全确定——A中没有出现的元素都可以选。C语言中的函数在接受数组参数时无法得知数组的元素个数，所以需要传一个已经填好的位置个数，或者当前需要确定的元素位置cur，代码如下：//不要关心那么多头文件啥意思，我用的基本上都是c风格的（对我们新生说的）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
void print_permutation(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++) { //尝试在A[cur]中填各种整数i
		int ok = 1;
		for(int j = 0; j < cur; j++)
		    if(A[j] == i) ok = 0; //如果i已经在A[0]~A[cur-1]出现过，则不能再选
		if(ok) {
			A[cur] = i;
			print_permutation(n, A, cur+1); //递归调用
		}
	}
}
int main()
{
	int n,a[20];
	scanf("%d",&n);
	memset(a,0,sizeof(a));
	print_permutation(n,a,0);
    return 0;
}

当然如果你会c++的话可以用c++的库函数next_permutation。但对于初学者我建议最好理解上面的，不要一开始就对库函数有依赖，对于我们新生我希望你们可以先打好c的基础，觉得自己还不错了，可以尝试的开始学习c++,但值得一说的是，学习不要图快，学好才是关键，基础要劳，这次小测试的题目我没有出好，太过简单了，我的错。这些都是题外话，关于库函数的使用，看下面代码，相信你就会了。

#include<cstdio>
#include<algorithm> //包含next_permutation
using namespace std;
int main( ) {
    int n, p[10];
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &p[i]);
    sort(p, p+n); //排序，得到p的最小排列
    do {
        for(int i = 0; i < n; i++) printf("%d ", p[i]); //输出排列p
        printf("\n");
    } while(next_permutation(p, p+n)); //求下一个排列
    return 0;
}