康拓展开式

骑猪看日落 2022-06-17 08:39 148阅读 0赞

**康托展开**是一个[全排列][Link 1]到一个[自然数][Link 2]的[双射][Link 3]，常用于构建[哈希表][Link 4]时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

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\] 实际意义就是：  设一串数字中第n个数为s\[n\]，   a\[i\]表示第n个数之后的数比s\[n\]小的数的个数。   看以下例子，便于理解

举例：

例如，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!

康托展开的逆运算

例1 \{1,2,3,4,5\}的 [全排列][Link 5]，并且已经从小到大排序完毕

(1)找出第96个数

首先用96-1得到95

用95去除4! 得到3余23

有3个数比它小的数是4

所以第一位是4

用23去除3! 得到3余5

有3个数比它小的数是4但4已经在之前出现过了所以第二位是5（4在之前出现过，所以实际比5小的数是3个）

用5去除2!得到2余1

有2个数比它小的数是3，第三位是3

用1去除1!得到1余0

有1个数比它小的数是2，第二位是2

最后一个数只能是1

所以这个数是45321

(2)找出第16个数

首先用16-1得到15

用15去除4!得到0余15

用15去除3!得到2余3

用3去除2!得到1余1

用1去除1!得到1余0

有0个数比它小的数是1

有2个数比它小的数是3 但由于1已经在之前出现过了所以是4（因为1在之前出现过了所以实际比4小的数是2）

有1个数比它小的数是2 但由于1已经在之前出现过了所以是3（因为1在之前出现过了所以实际比3小的数是1）

有1个数比它小得数是2 但由于1，3，4已经在之前出现过了所以是5（因为1，3，4在之前出现过了所以实际比5小的数是1）

最后一个数只能是2

所以这个数是1435

数组a\[3\]=\{1,2,3\};它的全排列为：123,132,213,231,312,321（从小到大排）

要计算其中某个数在哪个位置就可以用康拓展开式，如求231的下标是多少（从0开始）

#include <iostream>
    #include <cstring>
    using namespace std;
    long long factory[]={1,1,2,6,24,120,720,5040,40320,362880};
    long long Contor(char str[], int n)
    {
        long long sum = 0;
        for(int i = 0; i < n; i++)
        {
            long long s = 0;
            for(int j = i+1; j < n; j++)
            {
                if(str[i] > str[j]) 
                    ++s;//代表当前数后面比它小的数的个数
                    //比如1324,3后面比3小的数的个数有1个，1后面比1小的数的个数有0个
            }
            sum += s*factory[n-i-1];
        }
        return sum+1;//考虑是从0开始还是从1开始
    }
    int main()
    {
        char str[100];
        cin >> str;
        cout << Contor(str, strlen(str));
        return 0;
    }

[Link 1]: http://zh.wikipedia.org/w/index.php?title=%E5%85%A8%E6%8E%92%E5%88%97&action=edit&redlink=1
[Link 2]: http://zh.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E6%95%B0
[Link 3]: http://zh.wikipedia.org/wiki/%E5%8F%8C%E5%B0%84
[Link 4]: http://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8
[Link 5]: http://baike.baidu.com/view/1710135.htm