康托展开求全排列的某一个

描述 Description   
   输入两个自然数m,n 1<=n<=20，1<=m<=n! 
输出n个数的第m种全排列。


康托展开的公式
　　把一个整数X展开成如下形式：

　　X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!

　　其中，a为整数，并且0<=a[i] 此公式把序号X 与 排列一一对应起来了

正解：
一个序列a[1]..a[n]，能转换成逆序数列b[1]..b[n] （b[n]是没用的 一定是0）
其中b[i]表示a[i+1]到a[n]中有多少数比a[i]小
然后分别乘以 (n-1)! (n-2)!...1!
得到了一个数 就是这个序列的序号+1
可以证明序号的顺序就是全排列的顺序
所以反向推一下
把m div (n-1)! 求出第一个数的逆序数
再m:=m mod (n-1);
  m div (n-2)! 就是第二个数的逆序数

最后能倒推到b数组 再由b数组推到a 这个比较简单就不写了
记得m一开始要减1

网上的程序 仅供参考
var 
a:array[1..21]of int64; 
b:array[1..20]of integer; 
i,j,n:longint; 
m,k:int64; 
begin 
  readln(n,m); 
  m:=m-1; 
  a[1]:=1; 
  b[1]:=1; 
  for i:= 2 to n do 
   begin 
   a[i]:=a[i-1]*i; 
   b[i]:=i; 
   end; 
  for i:=n downto 2 do 
   begin 
     k:=m div a[i-1]; 
     m:=m mod a[i-1]; 
     write(b[k+1],' '); 
     for j:=k+1 to n-1 do 
    b[j]:=b[j+1]; 
   end; 
   writeln(b[1]); 
end. 


#include

using std::cout;

using std::endl;

using std::cin;

using std::cerr;

using std::ios;

#include 

using std::ofstream;

int main()

{

	ofstream outNiXu("NiXu.txt",ios::out);

	if(!outNiXu){

		cerr<<"File could not be opened"<		exit(1);

	}

	int x=0;

	cout<<"Enter a number:";

	cin>>x;

	int *a=new int[x];

	int *b=new int[x];

	for(int i=0;i	{

		a[i]=x-1-i;

		b[i]=0;

	}

	int c=0,z=0;

	while(1<2)

	{

		int d=0;

		int e=0;

		for(int l=0;l			b[l]=0;

		for(int k=0;k		{

			e=0;

			c=a[k];

			for(int l=0;l			{

				if(b[l]==0)

				{

					if(e==c)

					{

						b[l]=k+1;

						

					}

					e++;

				}

			}

			if(a[k]!=0)

				d=1;

		}	

		for(int y=0;y			outNiXu<		outNiXu<		z++;

		for(int m=0;m			if(a[m]!=0)

			{

				for(int n=0;n				a[n]=x-1-n;

				a[m]=a[m]-1;

				break;

			}

			if(d==0)

				break;

	}

	delete[] a;

	delete[] b;

	outNiXu<<"In total:  "<	return 0;

}