字典序法生成全排列

大家好，欢迎来到IT知识分享网。

/*
	用字典序法生成全排列
*/
#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);
}