本文共 1435 字,大约阅读时间需要 4 分钟。
其中,为整数,并且。
的意义参见举例中的解释部分
例如,3 5 7 4 1 2 9 6 8 展开为 98884。因为X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884.
解释:
排列的第一位是3,比3小的数有两个,以这样的数开始的排列有8!个,因此第一项为2*8!
排列的第二位是5,比5小的数有1、2、3、4,由于3已经出现,因此共有3个比5小的数,这样的排列有7!个,因此第二项为3*7!
以此类推,直至0*0!
int kontuo(int n, string a){// n为全排列位数 a为当前排列 int i, j, sum, t; sum = 0; for(i = 0; i < n; ++i){ t = 0; for(j = i+1; j < n; ++j){ if(a[i] > a[j]) ++t; } sum += t*fac(n-i-1); } return sum + 1;//计算的sum为a之前的序列数 返回加1即为a所在序列数}
既然康托展开是一个双射,那么一定可以通过康托展开值求出原排列,即可以求出n的全排列中第x大排列。
如n=5,x=96时:
首先用96-1得到95,说明x之前有95个排列.(将此数本身减去1)用95去除4! 得到3余23,说明有3个数比第1位小,所以第一位是4.用23去除3! 得到3余5,说明有3个数比第2位小,所以是4,但是4已出现过,因此是5.用5去除2!得到2余1,类似地,这一位是3.用1去除1!得到1余0,这一位是2.最后一位只能是1.所以这个数是45321.
string revKontuo(int sum,int n){//sum为待求排列所在位置序列 n为全排列位数 int i, j,mod,s,f,t; string ss = ""; sum = sum -1;//减一得到前面的康拓展开的结果 for(i = 1; i <= n; ++i){ t = 0; f = fac(n-i); s = sum/f; sum = sum%f; for(j = 1; j <= n; ++j){ if(!vis[j]){ if(s == 0) break;//这里两个语句位置不能颠倒 因为 关系到下面的 j还是j+1 --s; } } ss = ss + char(j+'0'); vis[j] = true; } return ss;}
注意:这里 为什么 逆序 依次除 (n-1)! 、 (n-2)! ... 我发现一个规律 就是 一以 1234为例 4! = 3*3! + 2*2! + 1*1! + 0*0!+1
后面的和加起来比最前面的阶乘小一,也就不会影响最前面的商的结果,逆序除最大项(n-1)! 得到的商 一定是康拓展开时候的(n-1)!的系数,
依次进行这样操作,最终每个系数都可以得到且正是康拓展开的结果
求阶乘long long fac(int n){ if(n == 0 || n == 1) return 1; return n*fac(n-1); }
转载地址:http://vmimi.baihongyu.com/