《康托展开和康托展开的逆运算》由会员分享，可在线阅读，更多相关《康托展开和康托展开的逆运算（2页珍藏版）》请在金锄头文库上搜索。
1、康托展开和康托展开的逆运算By_scy 2010-4-8 八数码问题不用康托展开判断重复8s，用康托展开判断重复30MS 。康托展开最大 最明显的作用就是在判断状态是否重复方面了，其实属于hash 的一个技巧。一、康托展开【问题背景】对于一个有n 个不同元素的集合 1,2,3,4,.,n的从小到大排序（从大 到小 同理）的全排列显然它有 n！项。如 n=4，那么就有 4！=4321=24项。与自然数 1，2，3，4，-n！与之一一对应。比如 1 4 四个数的全排列按字典序 如下： 1234：第一个 1243：第二个 1324：第三个 1342：第四个 1423：第五个 1432：第六个2134
2、：第七个 2143：第八个 2314：第九个 2341：第十个 2413：第 11 个 2431：第 12 个3124：第 13 个 3142：第 14 个 3214：第 15 个 3241：第 16 个 3412：第 17 个 3421：第 18 个4123：第 19 个 4132：第 20 个 4213：第 21 个 4231：第 22 个 4312：第 23 个 4321：第 24 个【主要问题】例 1：求 4132 是第几个排列？看上面就知道答案就是：20。 那么是怎么算的呢？解：总共 4 个数，所以 n=4.ans:=0; 第一个数是 4，研究比 4 小的并且还没有出现过的数有3 个
3、：1，2，3。那么 ans:=ans+ 3*(n-1)! 所以 ans:= ans+ 3* 3*2*1 =18 第二个数是 1， 研究比 1小的并且还没有出现过的数为 0 个。 那么 ans:=ans+ 0 * (n-2)!， 那么 ans 不变。第三个数是 3，研究比 3 小的并且还没有出现过的数为1 个：1，2。那么 ans:=ans+ 1* (n-3)!,那么 ans:=18+1* 1=19 第四个数是 2，研究比 2 小的并且还没有出现过的数为0 个。那么 ans 不变。其实最后 一个可以不研究了，比它大和比它小的全都出现过了。最后 ans 怎么等于 19啊？代 表它前面有 19 个排
4、列嘛，那么 4132 自己就是第 20 个罗（ 最后 ans:=ans+1）例 2：问 45231 是第几个排列？4 5 2 3 1ans:= 3*4! + 3*3! + 1*2! + 1*1! + 0*0! + 1 =94 练习第一题：找出 35142 在 15 从小到大全排序中的位置？第二题：找出 6482731在 18 从小到大全排列中的位置？第三题：找出 35142 在 15 从大到小全排序中的位置？第四题：找出 6482731在 18 从大到小全排列中的位置？二、康托展开的逆运算例 3：15 从小到大全排列中，找出第96 个排列？解：首先设 x1x2x3x4x5, (x1等于？不知道
5、 ) ，用 96-1 得到 95，表示 x1x2x3x4x5 前面 有 95 个序列。第一个数 x1，假设 x1 目前有 k 个比 x1 小的并且还没有出现过的数，那么k:= 95 div (n-1)! = 95 div 24=3, 也就是有 3 个比 x1 小并且没有出现过的数，那么 x1=4. 95 变成 95-324=23 第二个数 x2，假设 x2 目前有 k 个比 x2 小的并且还没有出现过的数，那么k:= 23 div (n-2)! = 23 div 6 = 3, 也就是有 3 个比 x2 小并且没有出现过的数，那 么 x2=5.（有 3 个数比它小的数是4，但 4 已经在之前出现
6、过了，所以是5）23 变成 23 3 * 6 = 5 第三个数用 23 去除 3! 得到 3 余 5 第四个数用 5 去除 2! 得到 2 余 1 第五个数就是最后还没有出现的那个。所以这个数是 45321 练习：第五题： 8 个数从小到大排序，求第28017个排列？第六题： 8 个数从大到小排序，求第14302个排列？注意 8 ！= 42320 http:/10.3.20.223/JudgeOnline/showproblem?problem_id=1038 noip2004 普及火星人http:/10.3.20.223/JudgeOnline/showproblem?problem_id=1148 8 数码问题http:/10.3.20.223/JudgeOnline/showproblem?problem_id=1209魔板 ioi96 http:/10.3.20.223/JudgeOnline/showproblem?problem_id=1212巧妙取量
