康托展开

发表于 分类于 阅读次数： 本文字数： 693 阅读时长 ≈ 3 分钟

介绍

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

运算

3 5 7 4 1 2 9 6 8展开为98884。
98884 = 2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!
排列的第一位是3，比3小的数有两个，以这样的数开始的排列有8!个，因此第一项为28!
排列的第二位是5，比5小的数有1、2、3、4，由于3已经出现，因此共有3个比5小的数，这样的排列有7!个，因此第二项为37!
以此类推，直至0*0!

逆运算

如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.

java 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public class MathUtils {
    public static Integer[] factorial = new Integer[11];
    static{
        factorial[0] = 0;
        factorial[1] = 1;
        for(int i = 2, len = factorial.length; i < len; i++){
            factorial[i] = factorial[i-1]*i;
        }
    }

    /**
     * 将cantor逆康托展开, 返回一个全排列
     * 如[1,2,3],1
     * 如[3,2,1],6
     * @param sequence 全排列中的元素序列
     * @param cantor 康拓展开值
     * @return 全排列
     */
    public static int[] deCantor(int[] sequence, int cantor){
        int len = sequence.length;
        if(len>10){
            throw new IllegalArgumentException("确保"+len+"不大于10");
        }
        if(cantor<=0 || cantor>factorial[len]){
            throw new IllegalArgumentException("确保"+cantor+"在[0,"+factorial[len]+"");
        }
        Arrays.sort(sequence);
        int[] num = new int[len];
        boolean[] mark = new boolean[len];

        cantor--;
        len--;
        int idx = 0;
        while(len!=0){
            int k = cantor/factorial[len];
            for(int i = 0; i <= k; i++){
                if(mark[i]){
                    k++;
                }
            }
            num[idx++] = sequence[k];
            mark[k] = true;
            cantor %= factorial[len--];
        }
        for(int i = 0, k = mark.length; i<k; i++){
            if(!mark[i]){
                num[k-1] = sequence[i];
                break;
            }
        }
        return num;
    }

    /**
     * 返回chars[]在全排列中是第几大的排列
     * 如[1,2,3]返回1
     * 如[3,2,1]返回6
     * @param chars 全排列
     * @return 康托展开的值
     */
    public static int enCantor(int... chars) {
        int len = chars.length;
        if(len>10){
            throw new IllegalArgumentException("确保"+len+"不大于10");
        }
        int[] low = new int[len];
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                if(chars[j]<chars[i] && j>i){
                    low[i]++;
                }
            }
        }

        int num = 0;
        for (int i = 0; i < len; i++) {
            num += low[i] == 0 ? 0 : low[i] * factorial[len-1-i];
        }
        return num+1;
    }

    public static BigInteger factorial(int n){
        int len = factorial.length;
        if(n<len){
            return BigInteger.valueOf(factorial[n]);
        }
        BigInteger result = BigInteger.valueOf(factorial[len-1]);
        for(int i = len; i <= n; i++){
            result = result.multiply(BigInteger.valueOf(i));
        }

        return result;
    }
}

参考资料