康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。
康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。
以下称第x个全排列是都是指由小到大的顺序。
X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0!
其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。
a[i]的意义参见举例中的解释部分
例如,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!
显然,n位(0~n-1)全排列后,其康托展开唯一且最大约为n!,因此可以由更小的空间来储存这些排列。由公式可将X逆推出对应的全排列。
康托展开的逆运算[编辑]
既然康托展开是一个双射,那么一定可以通过康托展开值求出原排列,即可以求出n的全排列中第x大排列。
如n=5,x=96时:
首先用96-1得到95,说明x之前有95个排列.(将此数本身减去!)
用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.
按以上方法可以得出通用的算法。
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
//阶乘
int fac[] = {1,1,2,6,24,120,720,5040,40320};
int kt(int n,int s[]){
int sum = 0,smallNum;
for(int i=0; i<n; i++){
smallNum = 0; //比当前数小的数
for(int j=i+1; j<n; j++)
if(s[i] > s[j])
smallNum++;
sum += smallNum * fac[n-i-1];
}
return sum;
}
void invKT(int n, int k, int s[]){
int t,j;
bool visit[10] = {false}; //需要记录该数是否已在前面出现过
for(int i=0; i<n; i++){
t = k/fac[n-i-1];
for(j=1; j<=n; j++){
if(!visit[j]){
if(t == 0) break;
t--;
}
}
s[i] = j;
visit[j] = true;
k %= fac[n-i-1];
}
}
int main() {
int arr[] = {1,3,2,5,4};
printf("%d\n", kt(5,arr));
int desArr[5];
invKT(5, 7, desArr);
for(int i=0; i<5; i++)
cout << desArr[i] << ",";
cout << endl;
//测试
// int testArr[] = {1,2,3,4,5};
// while(next_permutation(testArr,testArr+5)){
// for(int i=0; i<5; i++)
// cout << testArr[i] << ",";
// cout << endl;
// }
return 0;
}
分享到:
相关推荐
康托展开和康托展开的逆运算 康托展开是这样解释的——{1,2,3,4,...,n}表示 1,2,3,...,n 的排列,如 {1,2,3} 按从小到大排列一共 6 个,123 132 213 231 312 321,代表数字 1 2 3 4 5 6,也就是把 10 进制数与一个排列...
实现康托展开hash的代码,pascal语言通过将数组转变为数字
结合力扣第60题,第k个排列,进行康托展开和逆康托展开的学习。 题目描述:给出集合[1,2,…,n],其所有元素有n!种排列,按大小排列出所有情况,并一一标记,当n=3时,排列如下: “123” “132” “213” “231” ...
组合数学- 康托展开.rar
错用罗素悖论——康托在集合论中的两个逻辑性错误,欧阳耿,,从经典无穷理论体系中的缺陷入手,深入分析了罗素悖论与康托的实数集合不可数证明及康托定理 证明之间的本质性联系,发现康托在�
1975年度诺贝尔经济学奖获得者康托洛维奇的数学名著, 上册为“泛函分析”的第一部分--线性算子与线性泛函,共十一章,内容有拓扑空间与度量空间,向量空间,拓扑向量空间,赋范空间,线性算子与线性泛函,泛函的...
康托洛维奇不等式简证 康托洛维奇不等式简证 康托洛维奇不等式简证
数学方法论丛书-康托的无穷的数学和哲学.pdf
9.2.3康托展开逆运算 9.2.5魔板问题 9.2.6虫食算 9.2.2康托展开 9.2.8靶形数独 9.2.7 15数码问题 9.2.9斗地主 9.2.10Mayan游戏 全书章节 第01章 模拟算法免费 第02章 递归算法 第03章 枚举算法 第04章 递推算法 第...
用康托集的思路测量分形维度
谱康托测度的谱的性质,李汉巨,,本文研究了一类起源于实线上的函数迭代函数系统的谱康托测度的谱的性质.特别地,我们得到了一个谱康托测度的必要条件.我们的主要�
康托展开:这是一种将离散结构转换为连续结构的方法,可以用来简化九宫重排问题的解决过程。通过康托展开,可以将九宫格的状态转换为一维数组,从而更容易地进行搜索和分析。 蓝桥杯历届试题解法:蓝桥杯竞赛中的...
达最小值,这个问题我们简称规划L这个问题是线性规划中最重要问题之一,它在物资调配、运输等方面有着成功的应用.对于具体的物资调配或运输问题有我国创造的优秀的图上作业法.对“康――西问题”的一般解法,有大家熟知...
用于解决N数码问题,采用逆向BFS+逆序康托展开+打表,实现效率高。
Bijection_Pairing_N_N2(index_In,flag_Pair) 在 [0,...,K] 和 N^2 的一些持续增长的子集之间提供三种不同的显式双射(根据三种模式:康托或三角形、优雅或方形、二次幂- Odd 或 POTO 用于 2-adic 整数分解)。...
该天线采用康托集分形辐射单元,有效增加天线的阻抗带宽,使所设计的天线满足超宽带通信的需求.为了避免超宽带天线与传统的窄带系统之间的干扰,在共面波导接地面的顶部刻蚀一个U形槽,从而在5.1~5.9 GHz产生一个...
康托索大学