NOJ1103-全排列

全排列

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

比赛描述

全排列的生成就是对于给定的字符集或数集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。对给定的字符集中的字符规定一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后，或根据给定的数集中的大小关系，规定两个全排列的先后是从左到右逐个比较对应的数的大小，即依照字典序给出全排列。例如字符集{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

 

题目来源

NUPT

思路：非常简单的全排列问题。可以用DFS回溯求全排列，STL中有next_permutation(  )这个函数更加方便。一定要先进行一个排序！不然Test1就卡住了。另外要注意输出格式，行末不能有多余空格，否则会出现output limite exceed这个结果。

#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;

const int maxn = 8;
int a[maxn];

int cmp( const void* a, const void* b ) {
    return *( int* )a - *( int* )b;
} 

void printArray( int A[], int n ) {
    int i;
    //printf( "%d: ", ++count );
    for( i = 0; i < n - 1; i++ ) {
        printf( "%d ", A[i] );
    }
    printf( "%d", A[n - 1] );
    printf( "
" );
}

int main() {
    int n;
    scanf( "%d", &n );
    for( int i = 0; i < n; i++ ) {
        scanf( "%d", &a[i] );
    }
    qsort( a, n, sizeof( a[0]), cmp );
    do {
        printArray( a, n );
    }while( next_permutation( a, a + n ) );
    return 0;
}