几种全排列的算法(C语言实现)

/* 
 * 几种排列组合的算法
 */

#include<stdio.h>

int a[20];
int n;

//打印数组
void showArray(int *a)
{
	int i;
	for(i=1;i<=n;i++)
    	printf("%d",a[i]);
	printf("\n");
}

//翻转法
void overturn()
{
	int i,temp,temp1,temp2,j;
	int b[20];
	for(i=1;i<=n;i++)
		*(b+n-i+1)=*(a+i);
	showArray(b);
	for(i=1;i<=n;i++){
		//判断第一个数是否为1
		if(i==1 && b[i]!=i){
			temp=b[i];
			for(j=1;j<n;j++)
				b[j]=b[j+1];
			b[j]=temp;
			showArray(b);
			i=0;
			continue;
		}
    	//判断第二个数是否为1
		if(i==2 && b[i]!=i){
			temp1=b[i];
			temp2=b[i-1];
			for(j=1;j+2<=n;j++)
				b[j]=b[j+2];
			b[j]=temp1;
			b[j+1]=temp2;
			showArray(b);
			i=0;
			continue;
		}
       	//判断第三个数是否为1
		if(i==3 && b[i]!=i){
			temp=b[i];
			temp1=b[i-1];
			temp2=b[i-2];
			for(j=1;j+3<=n;j++)
				b[j]=b[j+3];
			b[j++]=temp;
			b[j++]=temp1;
			b[j]=temp2;
			showArray(b);
			i=0;
			continue;
		}
	}
}

//换位法
void changeSite()
{
	int i,temp,temp1;
	int b[20],max=0;
	int dir[20]={-1,-1,-1,-1,-1,-1};
	for(i=1;i<=n;i++)
		*(b+i)=*(a+i);
	showArray(b);
	while(1){
		max=0;
		b[max]=0;
		//寻找最大的活结点
    	for(i=1;i<=n;i++){
    		if(i+dir[i]>0 && i+dir[i]<=n && b[i]>b[i+dir[i]])
				max=b[i]>b[max]?i:max;
		}
    	if(max==0)
	    	break;
		//交换位置和方向
        temp=b[max];
    	b[max]=b[max+dir[max]];
        b[max+dir[max]]=temp;
		temp1=dir[max+dir[max]];
		dir[max+dir[max]]=dir[max];
        dir[max]=temp1;
		//改变比活结点大的数的方向
    	for(i=1;i<=n;i++)
    		if(b[i]>temp)
	    		dir[i]=-dir[i];
        showArray(b);
	}
}

//序数法(排出的序列为有序的)
//str:待排序的字符序列 n:首字符下标 len：字符串长度
void ordinal(char * str,int n,int len)
{
	int i;
	char temp;
	if(n==len)
		puts(str);
	for(i=n;i<len;i++){
		temp=str[i];
		str[i]=str[n];
		str[n]=temp;
		ordinal(str,n+1,len);
		temp=str[i];
		str[i]=str[n];
		str[n]=temp;
	}
}

void main()
{
	int i;
	char str[20];
	for(i=1;i<=4;i++)
		a[i]=i;
	a[0]=n=4;
	printf("对1234这四个数进行全排列\n");
	printf("翻转法:\n");
	overturn();
	printf("换位法:\n");
	changeSite();
	printf("序数法:\n");
	for(i=0;i<n;i++)
		str[i]=a[i+1]+'0';
	str[i]=0;
	ordinal(str,0,n);
}