康托展开 订阅
康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。 展开全文
康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。
信息
外文名
Cantor expansion
提出者
康托
应用学科
计算机科学
中文名
康托展开
适用领域范围
解决一些序列问题的算法
康托展开原理介绍
其中, 为整数,并且 。 表示原数的第i位在当前未出现的元素中是排在第几个z康托展开的逆运算既然康托展开是一个双射,那么一定可以通过康托展开值求出原排列,即可以求出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。按以上方法可以得出通用的算法。 [1] 
收起全文
精华内容
下载资源
问答
  • 康托展开

    2018-02-27 22:16:20
    康托展开

    康托展开

    康拓展开的结果为他的全排列中比他小的值得个数, 计算公式为:

    ANS = A[n] * (n - 1)! + A[n-1] * (n - 2)! + ...... + A[1] * 0! //A[n]表示其位上比他小的数的个数(不能再前面出现过)

    比如 465 在 其全排列中的位置为:

    ans = 0 * 2! + 1 * 1! + 0 * 0! = 0 + 1 + 0 = 1

    所以在其全排列中比他小的数只有一个(456)
    可知465在其全排列中的位置为2

    康托展开及其逆运算

    const int factor[] = {1,1,2,6,24,120,720,5040,40320};
    //康托展开 
    int cantor(char str[])
    {
        int ans = 0;
        int len = strlen(str);
    
        for(int i = 0; i < len; ++i)
        {
            int tmp = 0;
            for(int j = i + 1; j < len; ++j)
            {
                if(str[i] < str[j]) tmp ++; 
            }
    
            ans += tmp * factor[len - i - 1]; 
        }
        return ans;
    }
    
    //康拓逆展开
    
    vector cantor_reverse(int n, int m)
    {
        n--;
    
        vector<int> tmp, ans;
    
        for(int i = 1; i <= m; ++i) tmp.push_back(i);
    
        for(int i = m; i >= 1; ++i)
        {
            int r = n % factor[i - 1];
            int t = n / factor[i - 1];
    
            n = r;
            sort(tmp.begin(); tmp.end());
            ans.push_back(tmp[t]);
            tmp.erase(tmp.begin() + t);
         } 
        return ans;
     } 

    参考:http://blog.csdn.net/acdreamers/article/details/7982067

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,635
精华内容 654
关键字:

康托展开