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