codingmethod.cpp

来自「对于给定的$n$, 生成$[n]$的所有排列的算法。采用逆序数编码方法。」· C++ 代码 · 共 81 行

#include<stdio.h>
#include<math.h>
#define N 4
void main()
{
	int i,j,k,M=1,t,v;
    for(i=1;i<=N;i++)
	{
		M=M*i;                  /*阶乘的生成*/
	}
	int a[N],b[N-1];            /*a[]为最后要填充数字的位数，b[]为n[i]数*/
	for(i=0;i<M;i++)
	{

		for(j=0;j<N;j++)
		{
	    	a[j]=0;             /*对a[]所有位均赋值为零*/
		}
		t=i;
		for(j=0;j<N-1;j++)
		{
			b[j]=t%(j+2);          /*求b[]即书中a[]的值*/
			t=(t-b[j])/(j+2);
		}
		v=b[N-2];                  /*对b[n-1]赋值到v,并且把a[]中v位置填上n*/
		a[v]=N;
		for(k=N-1;k>0;k--)
		{
			if(k==1)
			{
				for(j=0;j<N;j++)
				{
					if(a[j]==0)
					{
						a[j]=1;    /*当最后一个位置是0时把1填充进去*/
						break;
					}
				}
			}
            if(k!=1)
			{
				v=0;                        /*v为从左起对空格数的统计*/
			    for(j=0;j<N;j++)
				{
					if(v==b[k-2] && (a[j]==0))         /*v的数目刚好和得到的b[]的数相同，并且在a[]中对应位置为0
						                                 否则循环到下一个非零位置把k的值负进去*/
					{
					   a[j]=k;
					   break;
					}
				    if(a[j]==0)v=v+1;             /*累计计算位置中空格的数目*/
				
				}
			}
		}
        for(j=0;j<N;j++)
		{
			printf("%d",a[j]);
			if(j==N-1)printf("\n");
		}
		
	}
}