lexorder.cpp

对于给定的$n$, 生成$[n]$的所有排列的算法。采用字典序编码。

#include<stdio.h>
void main(){
    int a[50]={0}, b[50]={0};
    int n,i,j,m,k,d,l,e;
    scanf("%d", &n);
    for(i=1;i<=n;i++){
		a[i]=i;
		printf("%d",a[i]);
    }
    printf("\t");
    for(;d<n;){
		d=0;

		for(j=1;j<n;j++)
			if(a[j]<a[j+1])
				k=j;     //k记录最后一个正序位置

		for(m=k+1, i=1;m<=n;m++)
			if(a[m]>a[k]){
				b[i]=a[m];
				i++;    
			}			//找到其后比它大的元素，用数组b[i]记录

		for(j=1;j<=i-1;j++)
			if(b[j]<b[1])
				b[1]=b[j];  //找到b[i]的最小元，记录到b[1]中

		for(m=k;m<=n;m++)
			if(a[m]==b[1]){
				l=m;
				e=a[k];
				a[k]=b[1];
				a[l]=e;
			}				//将a[k]和b[1]交换

		for(j=1;j<=(n-k)/2;j++){
			e=a[k+j];
			a[k+j]=a[n+1-j];
			a[n+1-j]=e;
		}					//将位置k后面的元素轮换

		for(i=1;i<=n;i++)
		    printf("%d",a[i]);
		printf("\t");		//输出

		for(i=1;i<=n;i++)
			if(a[i]==n+1-i)
				d++;}		//检验是否达到逆序排列
	}

//综上，算法是找到最后一个正序位置，将其后面比它大的最小元
//和它进行互换，然后通过对换使得其后面的元素按从小到大排列。
//最后达到逆序排列程序结束。

//在寻找最小元的时候，可以改进算法。