MENU

康托展开

April 15, 2021 • Read: 136 • 编程之路,Algorithm

康托展开原理&概念

  • 一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。
  • 康托展开:给出一个全排列,求它是所有全排列中的第几个。
  • 逆康托展开给出全排列长度和它是第几个全排列,求这个全排列。

计算公式及说明

$$ X = a_n(n-1)!+a_{n-1}(n-2)!+...+a_10! $$

说明:

一个$1\sim n$的全排列,从右往左数第$ i $位上的数记为$k_i$,初始有$n$个数的集合$[1,2,...,n]$$a_i$表示当前集合中小于$k_i$的数有几个,$a_i$计算完毕后把$k_i$从数组中去掉。计算时,从排列的最高位开始,即从$a_n$开始算。算完后把$k_n$去掉,再计算$a_{n-1}$以此类推。

举例:求$53241$的序号,即看$53241$前面有多少个排列。

  • 看第1位:$[5,3,2,4,1]$中小于$5$的有$4$个($1xxxx,2xxxx,3xxx,4xxxx$),共有$4*4!$个排列。
  • 看第2位:$[3,2,4,1]$中小于$3$的有$2$个($51xxx,52xxx$),共$2*3!$个
  • 看第3位:$[2,4,1]$中小于$2$的有1个($531xx$),共$1*2!$个
  • 看第4位:$[4,1]$中小于$4$的有1个($5321x$),共$1*1!$个
  • 第5位不用看了,没数了

综上所述,53241的序号是$4*4!+2*3!+1*2!+1*1! = 111$。

12345的序号是:$0*4! + 0*3!+0*2!+0*1! = 0$,康托展开的位数从$0$开始。

朴素代码

import java.util.*;
/**
 * 康托展开
 * @author CanYe 
 */
public class CantorExpansion{
    public static final int N = 100_0010;
    public static boolean[] used = new boolean[N];
    public static long[] factorial = new long[N];
    public static void main(String[] args) {
        int n = 5;
        String line = "53241";
        // 预处理阶乘
        initFactorial(n);
        long sum = 0;
        for (int i = n - 1; i > 0; i--) {
            // 计算ai
            int cur = line.charAt(n-1-i) - '0';
            int a = 0;
            for (int j = 1; j < cur; j++) {
                if(!used[j])    a++;
            }
            used[cur] = true;
            sum += a * factorial[i];
        }
        System.out.println(sum);
    }
    private static void initFactorial(int n) {
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i-1] * i;
        }
    }
}

外层循环$n$次,内层找数$n$次,时间复杂度是$O(n^2)$,

树状数组代码

通过树状数组进行优化:动态求给定区间的和。used函数用树状数组维护区间和(同理,用线段树也没问题就是代码有点长),用过的数取值0,没用过的取值1。则查询小于$k$中没有用过的数的个数为query(k-1)

import java.util.*;
/**
 * 康托展开 树状数组代码
 * @author CanYe 
 */
public class CantorExpansion {
    public static final int N = 100_0010;
    public static long[] factorial = new long[N];
    public static int[] c = new int[N];
    private static int n;
    public static void main(String[] args) {
        n = 5;
        String line = "53241";
        // 初始化树状数组
        for(int i = 1  ;i <= n ; i ++){
            add(i, 1);  // 用过的是0,没用的是1
        }
        // 预处理阶乘
        initFactorial(n);
        long sum = 0;
        for (int i = n - 1; i > 0; i--) {
            // 计算ai
            int cur = line.charAt(n-1-i) - '0';
            // 查询[1...cur-1]没有用的个数,用过的是0,没用的是1
            int a = query(cur - 1);
            add(cur, -1); // 1-1=0
            sum += a * factorial[i];
        }
        System.out.println(sum);
    }

    private static void initFactorial(int n) {
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i-1] * i;
        }
    }
    private static int query(int x){
        int res = 0;
        for(int i = x ; i >= 1 ; i -= lowbit(i))
            res += c[i];
        return res;
    }
    private static void add(int t, int x){
        for(int i = t ; i <= n ; i += lowbit(i))
            c[i] += x;
    }
    private static int lowbit(int x){
        return x & -x;
    }
}

外层循环$n$次,内层找数$O(\log n)$,时间复杂度是$O(n\log n)$,

逆康托展开

概念

公式的逆推。

举例:$n=5$,康托展开是$111$,求全排列。

  • 第1位:$111 / 4! = 4余15$,说明首位之后比首位小的数有$4$个,即第1位是$5$
  • 第2位:$15/3! = 2余3$,说明第二位之后比第二位小的数有$2$个,即第二位是$3$
  • 第3位:$3/2! = 1余1$,说明第三位之后比第三位小的数有$1$个,即第三位是$2$
  • 第4位:$1/1! = 1余0$,说明第四位之后比第四位小的数有$1$个,即第四位是$4$(前面的数都已经用了,依次向后找)
  • 第5位,剩下个$1$。

综上,全排列为$53241$

朴素代码

import java.util.*;

/**
 * 逆康托展开
 * @author CanYe
 */
public class InversionCantorExpansion{
    public static final int N = 10010;
    public static boolean[] used = new boolean[N];
    public static int[] factorial = new int[N];
    public static void main(String[] args) {
        int n = 5;
        int sum = 111;
        StringBuilder strbud = new StringBuilder();
        // 预处理阶乘
        initFactorial(n);
        int q, r = sum;
        for (int i = n-1; i > 0; i--) {
            q = r / factorial[i]; //商
            r = r % factorial[i]; //余数
            for(int j = q+1 ; j <= n ; j ++){
                if(!used[j]){
                    strbud.append(j);
                    used[j] = true;
                    break;
                }
            }
        }
        for(int j = 1 ; j <= n ; j ++){
            if(!used[j]){
                strbud.append(j);
                break;
            }
        }
        System.out.println(strbud.toString());
    }
    private static void initFactorial(int n) {
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i-1] * i;
        }
    }
}

树状数组代码

通过树状数组进行优化:动态求给定区间的和。我们要找的是已知$a$的区间$[a...x]$中,第一个没有用过的数假设为$k$,则$[a...k-1]$是连续的$0$,即$[a...k]$的和是$1$(用过的是0,没用过是1)。找$k$ → 二分,$mid$为中点,如果区间和$[a...mid] >= 1$,取$r=mid - 1$,则取$l=mid$

import java.util.*;
/**
 * 逆康托展开 树状数组代码
 * @author CanYe
 */
public class InversionCantorExpansion {
    public static final int N = 10010;
    public static long[] factorial = new long[N];
    public static int[] c = new int[N];
    private static int n;

    public static void main(String[] args) {
        n = 5;
        StringBuilder strbud = new StringBuilder();
        // 初始化树状数组
        long sum = 111;
        
        for (int i = 1; i <= n; i++) {
            add(i, 1); //用过的是0,没用过的是1
        }
        // 预处理阶乘
        initFactorial(n);
        long q, r = sum;
        for (int i = n - 1; i > 0; i--) {
            q = r / factorial[i]; //商
            r = r % factorial[i]; //余数
            // 二分找到[q+1...x]区间和为1的x的最小值
            int x = find((int) (q + 1), n);
            strbud.append(x);
            add(x, -1);

        }
        for (int j = 1; j <= n; j++) {
            if (query(j) == 1) {
                strbud.append(j);
                break;
            }
        }
        System.out.println(strbud.toString());
    }

    //二分找到[a...x]区间和为1的x的最小值
    private static int find(int a, int x) {
        int l = a, r = x;
        while(l < r){
            int mid = l + r >> 1;
            if(query(mid) - query(a-1) >= 1){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }

    private static void initFactorial(int n) {
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i-1] * i;
        }
    }

    private static int query(int x) {
        int res = 0;
        for (int i = x; i >= 1; i -= lowbit(i))
            res += c[i];
        return res;
    }

    private static void add(int t, int x) {
        for (int i = t; i <= n; i += lowbit(i))
            c[i] += x;
    }

    private static int lowbit(int x) {
        return x & -x;
    }
}
- - - 结束 - - -
  • 文章标题:康托展开
  • 文章链接:https://blog.canye365.cn/archives/385.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )