首页 > 代码库 > 康托展开:对全排列的HASH和还原,判断搜索中的某个排列是否出现过

康托展开:对全排列的HASH和还原,判断搜索中的某个排列是否出现过

题目:http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2297

前置技能:(千万注意是从0开始数的

康托展开表示的是当前排列在n个不同元素的全排列中的名次。比如213在这3个数所有排列中排第3。

 

那么,对于n个数的排列,康托展开为:技术分享

 

其中技术分享表示第i个元素在未出现的元素中排列第几。举个简单的例子:

 

对于排列4213来说,4在4213中排第3,注意从0开始,2在213中排第1,1在13中排第0,3在3中排第0,即:

 

技术分享,这样得到4213在所有排列中排第ans=20

 

代码实现:(从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和还原,判断搜索中的某个排列是否出现过