康托展开总结

这里写图片描述

这是一个九宫格，里面只有1到9这9个数字。有一些题目涉及到八数码问题，也就是九宫格问题。在九宫格里我们自然想到用广搜去解决一些问题。可是广搜的状态怎么表示呢？

可以用string啊，长度就是9个，每个字符就是相应的数字。上图就是”342157689” 但是string虽然方便但是却要消耗很多时间，答案是就是超时。那把它变成数字呢？那更爆炸，9位是十亿。其实9个数字的排列组合是9的阶乘，最多就30多万个。我们可以按照字典序将这些排列进行排序，那么自然 123456789就是第一位，最后一位是987654321。那么问题来了，342157689是排在第几位呢？这个时候，我们就隆重介绍康托展开了。

康托展开的公式是X=a[n](n-1)!+a[n-1](n-2)!+…+a[i]*(i-1)!+…+a[1]*0!

a[n]是以第n个数字开头的逆序数。通俗点就是第n个数字后面有多少个数字比它大。例如 342157689 第1位是3，3 2和3 1有两个逆序数。所以a[1]=2;这样做的原因很简单，因为知道这个数字的逆序数，就知道这个数字是哪一个了。3的后面有两个数字比他小，那么第一个数字肯定是3。4的后面也有两个数字比他小，因为3已经确定了，那么4就是第三大的数字，所以第二位就确定是第三大的数字就是4了。也就是说这个式子a[n](n-1)!+a[n-1](n-2)!+…+a[i]*(i-1)!+…+a[1]*0，可以映射出唯一的一个九宫格，也就是这个九宫格的排名。

当然我们这里以 123456789 为第一位，所1是第一位,2是第二位。如果我们让342175689为第一位，那么3就排第一，4就排第2，以此类推。 这里给以123456789为第一位的康托展开模板，这样就简单一点，数字本身就是他的排名。大部分八数码题目就是以123456789为第一位

/康托展开
int kangtuo(int a[3][3])
{
    int sum=0,num;
    for(int i=0;i<9;i++)
    {
        num=0;
        for(int j=i+1;j<9;j++)
        {
            if(a[i/3][i%3]>a[j/3][j%3])
                num++;
        }
        sum+=num*fac[8-i];
    }
    return sum;
}

那么从九宫格可以映射到排名，当然从排名也可以映射到相应的九宫格。对(n-1)!取余就可以得到第n个数字的排名a[n],注意这个排名是以a[n]位开始的后面的数列的排名，前面确定都要不要考虑。知道排名就知道第n个数字是什么了。很简单，给一个模板，仍然是123456789位第一位

void invkt(int k,int *s)
{
    memset(vis2,0,sizeof(vis2));
    for(int i=1;i<=9;i++)
    {
        int t=k/fac[9-i];
        int j;
        for( j=1;j<=9;j++)
        {
            if(!vis2[j])
            {
                if(t==0)
                    break;
                t--;
            }
        }
        s[i]=j;
        vis2[j]=true;
        k%=fac[9-i];
    }
}