本文只是基于使用的角度来做一些简单说明，不作证明！！ 康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序。 举个例子：
康托展开的公式为：
x=a[n](n-1)!+a[n-1](n-2)!+…+a[1]*0!，x代表比当前排列小的排列的个数，因此最终我们需要的答案就是x+1，其中a[i]表示当前排列里从i位置右侧算起，比i位置的数还要小的数的个数，注意i从左到右依次为n,n-1,n-2,…1。
求{1,5,4,3,2}的康托展开。
首位是1，1的右边比1小的数没有，所以a[5]=0，注意这里是a[5]而不是a[1],同理a[4]=3，a[3]=2，a[2]=1，a[1]=0;
所以x=0 * 4!+3 * 3!+2 * 2!+1 * 1!+0 * 0!=23，所以15432在所有包含12345的升序全排列中排在第24位！！！
代码如下：#include<bits/stdc++.h> using namespace std; //先预先算好0~9的阶乘，方便计算 int fac[10]={1,1,2,6,24,120,720,5040,40320,362880}; //x=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[1]*0!，注意i是从1~n，没有0 int Contor(char *a,int n) { int sum=0,small=0; for(int i=0;i<n;i++) { small=0; for(int j=i+1;j<n;j++) { if(a[j]<a[i]) { //计算第i位右边比该数还要小的数的个数 small++; } } sum+=small*fac[n-i-1]; //例如12345，i=0时实际上对应着5 //顺数第i位实际上对应着第n-i位 ，即a[n-i]=small,所以应该是small* ((n-i)-1)! //所以应该是small*fac[n-i-1] } return sum+1; } int main() { int n,t; char a[10]; cin>>n>>a; cout<<Contor(a,n); return 0; }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
