这篇文章上次修改于 218 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

算法学习笔记(10): 康托展开

可以求一个组合的全排列的名次

比如：对于序列1,2,3

则序列排名为 1 2 3；1 3 2； 2 1 3； 2 3 1； 3 1 2； 3 2 1

这个排列是按字典序排名的。

故依据康托展开，它是一个全排列到自然数的双射，也就是排列映射到排名，排名映射到排列，后者又称作康托逆展开。

求排名过程

对于排列 2 5 3 4 1，这个排列绝对大于以1开头的排列，有4！种。

对于第二位5，已经锁定了第一位为2，所以剩下四个数，要第二位更小，有3x3！种更小的排列。

以此类推有 4! + 3 x 3! + 2! + 1= 45 ,有45个比它小的，所以它是46名。

const int factorial[]={1,1,2,6,24,120,720,5040,40320,362880,3628800};//阶乘0-10
int cantor(int a[],int n){
		//cantor展开,n表示是n位的全排列，a[]表示全排列的数（用数组表示）
    int ans = 0,sum = 0;
    for(int i = 1;i < n;i++){
        for(int j = i + 1;j <= n;j++)
            if(a[j] < a[i])
                sum++;
        ans += sum * factorial[n - i];//累积
        sum = 0;//计数器归零
    }
    return ans + 1;
}

求排列过程

对于名次46，要找到排列 2 5 3 4 1

已知排列公式为

又因为 n!严格大于 1~n-1的阶乘和

所以整除向下取整即可求得位的值

static const int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};   // 阶乘
//康托展开逆运算
void decantor(int x, int n)
{
    vector<int> v;  // 存放当前可选数
    vector<int> a;  // 所求排列组合
    for(int i=1;i<=n;i++)
        v.push_back(i);
    for(int i=n;i>=1;i--)
    {
        int r = x % FAC[i-1];
        int t = x / FAC[i-1];
        x = r;
        sort(v.begin(),v.end());// 从小到大排序
        a.push_back(v[t]);      // 剩余数里第t+1个数为当前位
        v.erase(v.begin()+t);   // 移除选做当前位的数
    }
}

时间优化

使用树状数组可以加快计算逆序对的数量。复杂度从 O(N2) → O(NlogN)

八数码问题

八数码问题是指一个移动格子的小游戏，对于一个3x3的区域，有1~8编号的格子，它们只能相邻移动到空位，问最少几次可以排列完成。

显然你可以利用BFS，暴力搜索所有选择，因为走一步变成一个新的状态。然而对于一个BFS，它没有减枝，没有去除重复计算的部分，需要考虑重复计算，就需要保存所有状态的一个visited数组，然而如何对一个状态进行编码。这就用到了康托展开。

康托展开在此处被作为一个哈希函数，把八数码问题的不同排列状态哈希成一个数，这就可以用于处理。

Mai Icy