八数码问题

八数码问题

前提知识 康拓展开

用途

相当于hash存储序列,使用更加小的空间来存储排列。

公式

$X = a_n(n-1)!+a_{n-1}(n-2)+…+a_1*0!$,$a_i$表示当前未出现的数字是排在第几个元素。$0 \leq a_i < i,1 \leq i \leq n$

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int fac[maxn];
fac[0] = 1;
rep(i,1,max) fac[i] = fac[i-1]*i;
int cantor(){
int ans = 0;
rep(i,0,maxn){
int cnt = 0;
for(int k=i+1;k<maxn;k++){
if(vis[k]<vis[i]) cnt++;
}
ans += fac[n-i]*cnt;
}
return ans;
}

reference:https://blog.csdn.net/cyningsun/article/details/6797128