/*
用字典序法生成全排列
*/
#include<stdio.h>
#include<stdlib.h>
void generate_i(int *p,int n,int *i)
{
int j=n;
while(p[j-1]>=p[j]){
j--;
}
*i=j;
}
void generate_j(int *p,int n,int i,int *j)
{
int k=n;
while(p[i-1]>=p[k]){
k--;
}
*j=k;
}
void swap(int *a,int *b)
{
*a=(*a)^(*b);
*b=(*a)^(*b);
*a=(*a)^(*b);
}
void reverse(int *p,int i,int n)
{
int k;
for(k=0;k<(n-i+1)/2;k++){
swap(&p[k+i],&p[n-k]);
}
}
void print(int *p,int n)
{
int i;
printf("p ");
for(i=1;i<=n;i++){
printf("%d ",p[i]);
}
printf("\n\n");
}
void main()
{
int n,N,x,i,j,*p;
printf("请输入n:");
scanf("%d",&n);
p=(int*)malloc((n+1)*sizeof(n));
for(x=1;x<=n;x++){
p[x]=x;
}
print(p,n);
//求n的阶乘得N
for(x=n,N=1;x>1;x--){
N*=x;
}
for(x=0;x<N-1;x++){
generate_i(p,n,&i);
generate_j(p,n,i,&j);
swap(&p[i-1],&p[j]);
reverse(p,i,n);
print(p,n);
}
free(p);
scanf("%d",&n);
}