一、问题描述
【问题描述】输入整数N( 1 <= N <= 10 )，生成从1~N所有整数的全排列。
【输入形式】输入整数N。
【输出形式】输出有N!行，每行都是从1~N所有整数的一个全排列，各整数之间以空格分隔。各行上的全排列不重复。输出各行遵循“小数优先”原则, 在各全排列中，较小的数尽量靠前输出。如果将每行上的输出看成一个数字，则所有输出构成升序数列。具体格式见输出样例。
【样例输入1】1
【样例输出1】1
【样例说明1】输入整数N=1，其全排列只有一种。
【样例输入2】3
【样例输出2】
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
【样例说明2】输入整数N=3，要求整数1、2、3的所有全排列, 共有N!=6行。且先输出1开头的所有排列数，再输出2开头的所有排列数，最后输出3开头的所有排列数。在以1开头的所有全排列中同样遵循此原则。
【样例输入3】10
【样例输出3】
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 10 9
1 2 3 4 5 6 7 9 8 10
1 2 3 4 5 6 7 9 10 8
1 2 3 4 5 6 7 10 8 9
1 2 3 4 5 6 7 10 9 8
1 2 3 4 5 6 8 7 9 10
1 2 3 4 5 6 8 7 10 9
1 2 3 4 5 6 8 9 7 10
1 2 3 4 5 6 8 9 10 7
……………………
【样例说明3】输入整数N=10，要求整数1、2、3、……、10的所有全排列。上例显示了输出的前10行。
【运行时限】要求每次运行时间限制在20秒之内。超出该时间则认为程序错误。提示：当N增大时，运行时间将急剧增加。在编程时要注意尽量优化算法，提高运行效率。
【评分标准】该题要求输出若干行整数。
二、代码
#include<stdio.h>
int N;
int i,j;
int jiecheng[11];
int output[10];
int factorial(){
jiecheng[0]=1;
int i;
for(i=1;i<10;i++){
jiecheng[i]=i*jiecheng[i-1];
}
}
void print(){
int i=0;
for(i=0;i<N-1;i++)
printf("%d ",output[i]);
printf("%d\n",output[i]);
}
void find(){
for(i=N-2;i>=0;i--){
if(output[i]<output[i+1])
break;
}
int k1=i;
int temp_low=i+1;
for(i=k1+1;i<N;i++){
if(output[i]>output[k1]&&output[i]<output[temp_low])
temp_low=i;
}
int temp;
temp=output[k1];
output[k1]=output[temp_low];
output[temp_low]=temp;
for(j=k1+1,i=N-1;i>j;i--,j++){
temp=output[i];
output[i]=output[j];
output[j]=temp;
}
}
int main(){
factorial();
scanf("%d",&N);
int i;
for(i=0;i<N;i++){
output[i]=i+1;
}
print();
for(i=1;i<jiecheng[N];i++){
find();
print();
}
}
三、算法
这篇博客讲的比较详细
全排列的实现方法–递归&字典序
.
以数列p
0
p
1
…p
n-1
p
n
为例，具体算法思想分为以下4个步骤：
i）从数列右边开始，找到第一个小于它右边的数，即找到一个j，满足j=max{i|p
i
<p
i+1
}
ii）然后从p
j+1
开始，从p
j+1
~p
n
的范围里面大于p
j
的数之间，挑出最小的数，记为p
k
iii）调换pj和pk的位置，这时候这个数列就变成了p
0
p
1
…p
j-1
p
k
p
j+1
…p
k-1
p
j
p
k+1
…p
n-1
p
n
iv）把p
j+1
…p
k-1
p
j
p
k+1
…p
n-1
p
n
逆序，得到的p
0
p
1
…p
j-1
p
k
p
n
p
n-1
…p
j+1
即为当前数列的下一个数列
为什么可以这样子呢，我们把p0~pn拆分成两部分，p0~pj，p
j+1
~pn，算法步骤1和2就保证了找到刚好比p0~pj的下一个数列，然后我们只需要确保j+1~n最小即可；由算法步骤1可知，j+1~n是降序排列的，即使p[j],p[k]调换位置后也是如此，所以在算法步骤4里面对后面这段逆序，就使得j+1~n 变成了升序，也就是字典序最小