康托展开

康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。 \[ X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! \] 其中, a[i]为整数，并且0 <= a[i] <= i, 0 <= i < n, 表示当前未出现的的元素中排第几个，这就是康托展开

举个例子说明。 在（1，2，3，4，5）5个数的排列组合中，计算 34152的康托展开值。

首位是3，则小于3的数有两个，为1和2，a[5]=2，则首位小于3的所有排列组合为 a[5](5-1)! 第二位是4，则小于4的数有两个，为1和2，注意这里3并不能算，因为3已经在第一位，所以其实计算的是在第二位之后小于4的个数。因此a[4]=2 第三位是1，则在其之后小于1的数有0个，所以a[3]=0 第四位是5，则在其之后小于5的数有1个，为2，所以a[2]=1 最后一位就不用计算啦，因为在它之后已经没有数了，所以a[1]固定为0 根据公式： X = 2 4! + 2 * 3! + 0 * 2! + 1 * 1! + 0 * 0! = 2 * 24 + 2 * 6 + 1 = 61 所以比 34152 小的组合有61个，即34152是排第62。

八数码难题（BFS剪枝）

P1379 八数码难题 - 洛谷 | 计算机科学教育新生态

在 3×3 的棋盘上，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字。棋盘中留有一个空格，空格用 0 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局 和 目标布局，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

#include<bits/stdc++.h>
using namespace std;

// 状态结构体
struct node{
	int x,y,steps;
	int ctVal;
	int a[4][4];
};

// 0-10的阶乘
const int f[] = {1,1,2,6,24,120,720,5040,40320,362880};
const int dirx[] = {1,-1,0,0};
const int diry[] = {0,0,1,-1};

// 某个排列是否出现过
bool visct[10000000];
// 起点和终点
string s,t;
int tt;

// 康托展开
// 即将 某个排列 映射 到 某个数字（第几个排列）
int cantor(string s){
	bool vis[10];
	memset(vis,false,sizeof(vis));
	int res = 0;
	int cnt = s.length()-1;
	for(int i = 0 ; i < s.length() ; i ++){
		int low = 0;
		vis[s[i]-'0'] = true;
		for(int j = 0 ; j < s[i] - '0' ; j ++){
			if(!vis[j]) low++;
		}
		res += f[cnt--]*low;
	}
	return res;
}

void bfs(){
	queue<node> q;
	// 初始化起点
	node temp;
	temp.steps = 0;
	temp.ctVal = cantor(s);
	visct[temp.ctVal] = true;
	for(int i = 1 ; i <= 3 ; i ++){
		for(int j = 1 ; j <= 3 ; j ++){
			temp.a[i][j] = s[(i-1)*3 + (j-1)] - '0';
			if(s[(i-1)*3 + (j-1)] == '0'){
				temp.x = i;
				temp.y = j;
			}
		}
	}
	q.push(temp);
	
	tt = cantor("123804765");
	while(!q.empty()){
		node fr = q.front(); q.pop();
		// 如果找到，退出
		if(fr.ctVal == tt){
			cout<<fr.steps;
			break;
		}
		node nex; string str;
		for(int i = 0 ; i < 4 ; i ++){
			nex.x = fr.x + dirx[i];
			nex.y = fr.y + diry[i];
			if(!(nex.x >= 1 && nex.x <= 3 && nex.y >= 1 && nex.y <= 3)) continue;
			nex.steps = fr.steps + 1;
			memcpy(nex.a,fr.a,sizeof(nex.a));
			swap(nex.a[fr.x][fr.y],nex.a[nex.x][nex.y]);
			str = "";
			for(int i = 1 ; i <= 3 ; i ++){
				for(int j = 1 ; j <= 3 ; j ++){
					str += char(nex.a[i][j] + '0');
				}
			}
			nex.ctVal = cantor(str);
			// 如果康托展开值重复，说明之前出现过更优解
			if(!visct[nex.ctVal]){
				q.push(nex);
				visct[nex.ctVal] = true;
			}
		}
	}
}

int main(void){
	cin>>s;
	bfs();
	return 0;
}