八数码问题

前提知识 康拓展开

用途

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

公式

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

实现

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