全排列 NOJ 1103

全排列

时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 1028 测试通过 : 258

题目描述

全排列的生成就是对于给定的字符集或数集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。对给定的字符集中的字符规定一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后，或根据给定的数集中的大小关系，规定两个全排列的先后是从左到右逐个比较对应的数的大小，即依照字典序给出全排列。例如字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
给定n个整数，现请编程求它们所有的全排列。

输入

输入包括两个行，第一行给出正整数n( 0 < n <=8), 第二个是 n个整数（大小范围：[-10^4, 10^4]）。

输出

按字典序输出这n个整数的全排列，每一行给出一个全排列。

样例输入

3
1 23 88

样例输出

1 23 88
1 88 23
23 1 88
23 88 1
88 1 23
88 23 1

分析：枚举所有排列的另一个方法是从字典序最小排列开始，不停调用"求下一个排列的函数"，如何求下一个排列呢？C++的STL中提供了一个库函数next_permutation。

实现代码如下：

#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,p[9];
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&p[i]);
    sort(p,p+n);
    do{
        for(int i=0;i<n;i++)  if(i==0) printf("%d",p[i]); else printf(" %d",p[i]);
        printf("
");
    }while(next_permutation(p,p+n));
    return 0;
}