关于康托展开的用途及写法

写法"/>

关于康托展开的用途及写法

在处理八数码这一类需要用到全排列的问题的时候， 存储往往是一个难题， 因为明明只有n!种情况， 数字的长度却有n， 用数组是肯定不行的。 这个时候， 康托展开就派上了用场， 当然， 在条件允许的情况下map不失为一个好的处理方法。

康托展开： 把满足0 <= P < (n+1)!的整数写成P = an*n! + an-1 * (n-1)! + ... + a2 * 2! + a1 * 1!(0 <= ai < i, i = 1,2,3...)的形式称为把P进行康托展开。

那么对于一个普通的数， 我们可以在O(L)的时间内将它进行康托展开， 只要用i!不停地试除就可以了。

不过首先要预处理出阶乘的数组：

int fac[15];
void first()
{fac[0] = 1;for (int i = 1; i <= 12; ++i)fac[i] = fac[i-1] * i;
}

我们现在只考虑int范围内的数， 因此12! = 479001600就是极限了。

void cantor(int x)
{int s[15], st;printf("%d = ", x);for (int i = 12; i; i--)if (fac[i] <= x)//求最高位{st = i;break;}for (int i = st; i; i--){s[i] = x / fac[i];//s[i]记录当前位的数字x -= s[i] * fac[i];}for (int i = st; i; i--){printf("%d*%d!", s[i], i);if (i != 1) printf(" + ");}putchar('\n');
}

但是只是对于一个数的康托展开是没有意义的， 我们需要处理的是一个n的全排列， 将这个排列变成一个排名， 就需要用到求逆序对的方法。
例如， 对于9的全排列564893217， 其相应的排名就是184190， 其中：
对于首位5， 后面有4、3、2、1四个数比它小， 而这时开头的排列有8!个， 因此ans += 4 * 8!;
然后是6， 后面同样有4、3、2、1四个数， 这时开头的排列有7!个， 因此ans += 4 * 7!;
以此类推， 有184190 = 4 * 8! + 4 * 7! + 3 * 6! + 4 * 5! + 4 * 4! + 2 * 3! + 1 * 2! + 0 * 1!;所以可以得到代码：

int cantor_change(int x)
{int s[15], len = 0, ans = 0;while(x){s[++len] = x % 10;x /= 10;}//计算x的位数for (int i = len; i; i--){int tmp = 0;for (int j = i - 1; j; j--)if (s[i] > s[j]) ++tmp;//求逆序对个数ans += fac[i-1] * tmp;}return ans;
}

当然， 新的有价值的问题也出现了， 对于一个n的全排列， 求第x大的那个排列。 
这就是康托展开的逆运算， 处理八数码问题的时候可以用这个方法还原棋盘。 
对于一个n的全排列， 假设我们已经固定了第一项， 那么剩下的排列方式还有(n-1)!种， 而第一项有n种选择， 那么第一项为m时， 该排列的排名在(m-1)*(n-1)!至m*(n-1)!之间， 且这个是可以推广的， 对于后面的n-2,n-3等等同样有效。 因此， 我们每一次用x除以(n-i)!， 记得到的商为k， 那么后面的i项中有k项小于当前项， 我们可以用一个数组标记已使用过的数字， 每次在未标记过的数中找出符合当前要求的数即可。 
例子：x = 2048, n = 9;
 首先， x / 8! = 0， 故第一位为1； 
x / 7! = 0， 第二位为2； 
x / 6! = 2， 则后面有两个数小于当前位， 应当为3和4， 故当前位为5， x %= 6! = 608； 
x / 5! = 5， 后面3,、4、6、7、8都小于当前位， 故为9， x %= 5! = 8；
以此类推， 最终可得排列：125936487；

void cantor_inv(int x, int n)
{x--;int flag[10], s[10];for (int i = 1; i <= n; ++i)flag[i] = 0;for (int i = 1; i <= n; ++i){int tmp = x / fac[n-i], now = 0;x %= fac[n-i];for (int j = 1; j <= n; ++j){if (!flag[j]){if (now == tmp){flag[j] = 1;s[i] = j;break;}++now;}}}for (int i = 1; i <= n; ++i)printf("%d", s[i]);putchar('\n');
}

那么， 关于排列的处理就有了新的方法， 不用担心空间会爆的问题了。

推荐练习：codevs2037魔板