首页 > 代码库 > 康托展开：对全排列的HASH和还原，判断搜索中的某个排列是否出现过
康托展开：对全排列的HASH和还原，判断搜索中的某个排列是否出现过
题目：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2297
前置技能:（千万注意是从0开始数的
康托展开表示的是当前排列在n个不同元素的全排列中的名次。比如213在这3个数所有排列中排第3。
那么，对于n个数的排列，康托展开为：
其中
对于排列4213来说，4在4213中排第3，注意从0开始，2在213中排第1，1在13中排第0，3在3中排第0，即：
代码实现：(从0开始计数)
//康托展开 LL Work(char str[]) { int len = strlen(str); LL ans = 0; for(int i=0; i<len; i++) { int tmp = 0; for(int j=i+1; j<len; j++) if(str[j] < str[i]) tmp++; ans += tmp * f[len-i-1]; //f[]为阶乘 } return ans; //返回该字符串是全排列中第几大，从1开始 }
康托展开的逆运算：就是根据某个排列的在总的排列中的名次来确定这个排列。比如：
求1234所有排列中排第20的是啥，那么就利用辗转相除法确定康托展开中的系数，然后每次输出当前未出现过的第
代码实现康托展开逆运算：
//康托展开逆运算 void Work(LL n,LL m) { n--; vector<int> v; vector<int> a; for(int i=1;i<=m;i++) v.push_back(i); for(int i=m;i>=1;i--) { LL r = n % f[i-1]; LL t = n / f[i-1]; n = r; sort(v.begin(),v.end()); a.push_back(v[t]); v.erase(v.begin()+t); } vector<int>::iterator it; for(it = a.begin();it != a.end();it++) cout<<*it; cout<<endl; }
康托展开：对全排列的HASH和还原，判断搜索中的某个排列是否出现过
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。