康托展开原理&概念
- 一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。
- 康托展开：给出一个全排列，求它是所有全排列中的第几个。
- 逆康托展开：给出全排列长度和它是第几个全排列，求这个全排列。
计算公式及说明
$$ 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;
}
}
- - - 结束 - - -