写法"/>
关于康托展开的用途及写法
在处理八数码这一类需要用到全排列的问题的时候, 存储往往是一个难题, 因为明明只有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魔板
更多推荐
关于康托展开的用途及写法
发布评论