解释原理处理问题八数字问题
说明康托展开是一种特殊的散列函数。 纸箱展开可以完成如下图所示的作业
状态012345678012345687012345768012345768012345786…876543210 cantor 0123…362880-1的第一行是0 ~ 8这9个数字的全排列，共有9！=362880个，从小到大排序。 第二行是与各数组对应的位置，例如最小的{012345678}位于第0个位置，最大的{876543210}位于最后的362880 - 1的位置。
函数Cantor ()输入包含第一行的数组，其Cantor值(即对应于第二行的数值Cantor ) )的复杂度为o ) n2 )，n实现计算为集合中元素的个数的功能。
原理例) 2143判断是{ 1，2，3，4 }的所有排列中第二大的数。
计算2143前面排列的数组数，可以将问题转换为以下数组之和。
)1)顶部小于2的所有数组。 只有一个数小于2，后面三个数的排列是3 * 2 * 1=3！ 个，写1 * 3！=6)2) 1位为2，2位小于1的所有数组。 不，写0 * 2！=0。 )3)前两位为21且第三位小于4的所有数组。 只用三个数(2134 )，写为1 * 1！=1。 )前三位为214且第四位小于3的所有数组。 不，写0 * 0！=0。 合计：1 * 3！ 0 * 2！ 1 * 1！ 0 * 0！=7，因此2143是第八大数字。 如果用int visited[24]数组记录各数组的位置，则{2143}为visited[7]； 第一次访问该数组时，visited[7]=1； 再次访问该阵列时，如果发现visited[7]=1，则表示已经处理，进行繁重的判断。
根据上面的例子得到纸箱展开式。
如果将基于一个集合的全部排列按词典顺序排列，则第x个要素的计算公式如下
x=a[n]*(n-1 )！ a[n-1]*(n-2 )！ …a[I]*(I-1 )！ … a[2] * 1！ a[1] * 0！ 其中，a[i]表示在当前未出现的元素中，有原来数量的第I个(从0开始)，0=a[I]I ) )1=In )
上述过程的逆过程是完全相反的展开。 在某个集合的所有数组中，输入数字k，返回第k个大数组处理问题八数字问题BFS Cantor。 在3 * 3的棋盘上放置编号1 ~ 8的8个方块，每个方块占一格，还有另一个空间。 与空间相邻的数字框可以移动到空间中。 任务1 )指定初始棋局和目标棋局，计算最小的移动步数； 任务2 :输出数字移动序列。
//输入：1 2 3 0 8 4 7 6 5
1 0 3 8 2 4 7 6 5
//输出： 2
# include bits/stdc.hconstintlen=362880； //一共9个！=362880种using namespace std； struct node{int state[9]； //记录八个数字排列，即记录一个状态int dis记录到起点的距离； int dir [4] [2]={-1，0 }、{0，-1}、{ 1，0 }、{ 0，1 }； //左、上、右、下、顺时针，左上为(0，0 )； int visited[LEN]={0}； //各状态对应的记录，cantor )函数对其进行计数，沉重地判定intstart(9)。 //开始状态int goal[9]； //目标状态longint factory [ ]={ 1，1，2，6，24，720，5040，40320，362880 }； OOLcantor(intstr[]，int n ) {long result=0； for(intI=0； i n； I ) {int counted=0； for(intj=I1； j n； j () if ) str[I]str[j] ) counted； }result =counted * factory[n - i - 1]； (if (！ visited [ result ] (visited [ result ]=1； 返回1； }elsereturn 0； (}int bfs ) ) {node head； memcpy(head.state，start，sizeof ) head.state )； head.dis=0； queuenodeq； cantor(head.state，9 )； q.push (头)； while (！ q.empty () {head=q.front； if(memcmp(head.state，goal，sizeof ) goal ) )==0)返回head.dis； q.pop (； int z； for(z=0； z 9； z//找到了寻找此状态种元素0的位置if (head.state [ z ]==0) break； int x=z%3； //横坐标int y=z/3； //纵坐标for(intI=0； i 4； I () /左、上、右、下，四种变化int newx=x dir[i][0]； //元素0迁移后的新坐标int newy=y dir[i][1]； int nz=newx 3 * newy； //转换为一维if (newx=0newx3newy=0ne wy3 ) )//未越界的node newnode； memcpy(newnode，head，sizeof ) structnode )； //复制此新状态swap (newnode.state[nz]，new node.state [ NZ ] )； 将//0移动到新位置newnode.dis； if(cantor(newnode.state，9 ) ) /铁路超高展开中较重的q.push ) newnode )； //对新状态进行排队}} }return -1； ///未找到}int main () for ) ) intI=0； i 9； I ) cin start[i]； //初始状态for(intI=0； i 9； I ) cin goal[i]； //目标状态int num=bfs (； if (数字！=-1 ) cout num endl； else cout 'Impossible' endl； 返回0； }//1 2 3 0 8 4 7 6 5 1 0 3 8 2 4 7 6 5