52梯控论坛

标题: 康拓编码与解码 [打印本页]
作者: ok120    时间: 2018-12-26 12:43
标题: 康拓编码与解码

一、康托展开：全排列到一个自然数的双射

X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!

ai为整数，并且0<=ai<i(1<=i<=n)

适用范围：没有重复元素的全排列


二、全排列的编码：

{1,2,3,4,...,n}的排列总共有n!种，将它们从小到大排序，怎样知道其中一种排列是有序序列中的第几个？

如 {1,2,3} 按从小到大排列一共6个：123 132 213 231 312 321。想知道321是{1,2,3}中第几个大的数。

这样考虑：第一位是3，小于3的数有1、2 。所以有2*2!个。再看小于第二位，小于2的数只有一个就是1 ，所以有1*1!=1 所以小于32

的{1,2,3}排列数有2*2!+1*1!=5个。所以321是第6个大的数。2*2!+1*1!是康托展开。（注意判断排列是第几个时要在康托展开的结果后+1）

再举个例子：1324是{1,2,3,4}排列数中第几个大的数：第一位是1小于1的数没有，是0个，0*3!，第二位是3小于3的数有1和2，但1已经在第一位了，所以只有一个数2，1*2! 。第三位是2小于2的数是1，但1在第一位，所以有0个数，0*1!，所以比1324小的排列有0*3!+1*2!+0*1!=2个，1324是第三个大数。

又例如，排列3 5 7 4 1 2 9 6 8展开为98884，因为X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884.

解释：

排列的第一位是3，比3小的数有两个，以这样的数开始的排列有8!个，因此第一项为2*8!

排列的第二位是5，比5小的数有1、2、3、4，由于3已经出现，因此共有3个比5小的数，这样的排列有7!个，因此第二项为3*7!

以此类推，直至0*0!


[cpp] view plain copy




  • #include<cstdio>  
  • const int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};///阶乘  
  •   
  • int KT(int s[], int n)  
  • {  
  •     int i, j, cnt, sum;  
  •     sum = 0;  
  •     for (i = 0; i < n; ++i)  
  •     {  
  •         cnt = 0;  
  •         for (j = i + 1; j < n; ++j)  
  •             if (s[j] < s) ++cnt;  
  •         sum += cnt * fac[n - i - 1];  
  •     }  
  •     return sum;  
  • }  
  •   
  • int main()  
  • {  
  •     int a[] = {3, 5, 7, 4, 1, 2, 9, 6, 8};  
  •     printf("%d\n", 1 + KT(a, sizeof(a) / sizeof(*a))); ///1+98884  
  • }  


三、全排列的解码

如何找出第16个（按字典序的）{1,2,3,4,5}的全排列？

1. 首先用16-1得到15

2. 用15去除4! 得到0余15

3. 用15去除3! 得到2余3

4. 用3去除2! 得到1余1

5. 用1去除1! 得到1余0

有0个数比它小的数是1，所以第一位是1

有2个数比它小的数是3，但1已经在之前出现过了所以是4

有1个数比它小的数是2，但1已经在之前出现过了所以是3

有1个数比它小的数是2，但1,3,4都出现过了所以是5

最后一个数只能是2

所以排列为1 4 3 5 2


作者: 老二大哥呢    时间: 2018-12-26 13:40
小手一抖，积分到手！
作者: xiexiaohu    时间: 2018-12-26 13:43
高手
作者: swnning    时间: 2018-12-26 16:10
厉害了，，，，，，，
作者: 125615dd    时间: 2018-12-26 18:16
谢谢楼主，共同发
作者: 胆小的鱼    时间: 2018-12-26 18:37
莫名其妙，不知所云！
作者: wsc    时间: 2018-12-26 20:15
太高深，，，，，，，，，
作者: dtsuifeng    时间: 2018-12-26 20:42
只说了一片叶子，看不见大树
作者: 爷爷    时间: 2018-12-27 07:33
小手一抖，积分到手！
作者: swnning    时间: 2018-12-28 16:04
我是来学习的，，，，
作者: luanwuzhong    时间: 2018-12-30 18:30
感觉这个是比较专业的
作者: 380977992    时间: 2018-12-30 19:08
我是来学习的
作者: 宇宙无限    时间: 2019-1-4 18:39
真没看懂。
作者: songqq924    时间: 2019-1-4 20:20
牛逼牛逼牛逼
作者: 380977992    时间: 2019-1-4 23:07
我差一点了； 马上回贴。发俩帖子。
作者: mxy0305    时间: 2019-1-6 14:29
作者: dlchy1958    时间: 2019-1-6 16:33
小手一抖，积分到手！
作者: 380977992    时间: 2019-1-6 18:53
路过，学习下
作者: 一步一趋    时间: 2019-1-15 11:58
说的很专业  但是完全看不懂
作者: 270497470    时间: 2019-1-15 15:27
不知所云
作者: viewyou    时间: 2019-1-15 15:57
好贴！！！！！！！！！！！！！！！！！！
作者: gycfy    时间: 2019-1-15 16:59
作者: 黑煞神    时间: 2019-1-19 08:25
看都看不懂
作者: chushanchao    时间: 2019-1-19 08:38
作者: 爷爷    时间: 2019-1-20 21:21
小手一抖，积分到手！
作者: yuwenyongfei    时间: 2019-1-20 23:07
看不懂！看来需要加强学习
作者: tsjinxin    时间: 2019-1-21 00:01
完全看不懂的我  陌陌的路过啊
作者: guduqiang    时间: 2019-1-21 00:30
小手一抖，积分到手！
作者: 270497470    时间: 2019-1-25 16:54
作者: iloveziyi    时间: 2019-2-26 14:08
没看明白！
作者: 270497470    时间: 2019-2-26 14:24
举个数据，要不然不知所云
作者: 313456766    时间: 2019-2-26 14:52
小手一动 积分到手 我不也不懂
作者: pm3tikong    时间: 2019-2-26 19:06
谢谢楼主，看不懂
作者: redevil    时间: 2019-2-26 19:44
高手大神,高手大神
作者: 38816    时间: 2019-2-26 21:39
这个才是绝对的科学计算
作者: 爷爷    时间: 2019-2-27 09:17
不错不错，很好哦
作者: AK_ming    时间: 2019-3-3 15:35
超级牛啊   是算法吗
作者: jxjaxa    时间: 2019-3-4 20:30
这个论坛挺不错的，还有软件可以用
作者: jxjaxa    时间: 2019-3-6 16:53
我只是领取软件的，啥数据不会哦
作者: BG4XWD    时间: 2019-3-6 22:04
学习学习谢谢分享！
作者: 爷爷    时间: 2019-3-8 08:32
小手一抖，积分到手！
作者: 东东大事    时间: 2019-3-11 11:15
我是进来学习的
作者: myjay5    时间: 2019-3-11 21:13
看不懂 路过~
作者: guopeng861    时间: 2019-3-12 09:51
帮帮顶顶！！
作者: mcyclub    时间: 2019-3-12 10:05
没上好学，看不懂。。。。。。
作者: mch_sjz    时间: 2019-3-12 10:24
小手一抖，积分到手！
作者: 爷爷    时间: 2019-3-20 15:50
看帖回帖是美德！
作者: lby810922    时间: 2019-3-27 09:41
太高级了  看不明白
作者: 华丽转身    时间: 2019-3-29 15:46
小白 完全蒙蔽 了啊
作者: 姜华    时间: 2019-3-29 19:32
高深莫测 重要是看不懂
作者: 赵三哥    时间: 2019-3-29 22:04
小手一抖，积分到手！
作者: 112521107    时间: 2019-3-29 22:14
小学文化，看不懂奥
作者: ywd683    时间: 2019-4-4 06:58
谢谢楼主，共同发
作者: a544983555    时间: 2019-4-5 17:18
小手一抖，积分到手
作者: joy1997881    时间: 2019-4-5 23:56
611m611m611m611m
作者: 赵氏开锁    时间: 2019-4-6 14:29
莫名其妙，不知所云！
作者: 皮皮    时间: 2019-4-6 15:11
小学毕业的我，看不懂
作者: 老三    时间: 2019-4-6 21:26

小手一抖，积分到手！
作者: 飞毛腿    时间: 2019-4-27 21:22
好专业，看不懂
作者: mcyclub    时间: 2019-4-29 09:15
这个是好数据！！！！！！！！！
作者: squlla    时间: 2019-4-29 12:20
作者: icicic    时间: 2019-4-29 13:52
不错，    是个好贴！   vb
作者: ts1001    时间: 2019-4-29 15:21
小手一抖，积分到手！
作者: flash100    时间: 2019-5-5 11:04
看不懂啊         
作者: yanggui    时间: 2019-5-6 09:35
DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
作者: xinchao0326    时间: 2019-6-6 00:03
提示: 作者被禁止或删除 内容自动屏蔽
作者: 188178785    时间: 2019-6-6 06:19
我们都要好好的
作者: aldrich    时间: 2019-6-11 15:38
看不懂
作者: liuziming52    时间: 2019-7-4 19:02
这个算法是算哪的？
作者: 铜雀    时间: 2019-7-10 10:00
不明觉厉！！！
作者: admin    时间: 2019-7-11 21:48
作者: yhj1    时间: 2019-7-12 10:02
作者: bigfeng_0_0    时间: 2019-12-19 13:56
不懂，我是来学习的
作者: 24886924叶    时间: 2019-12-20 08:01

小手一抖，积分到手
作者: lzg6876999    时间: 2019-12-20 08:07

我是来学习的
作者: lzg6876999    时间: 2019-12-20 13:17
我是来学习滴
作者: bigfeng_0_0    时间: 2019-12-20 15:08
我是来学习的
作者: lzg6876999    时间: 2019-12-20 15:08

前来学习学习
作者: wjy123    时间: 2019-12-20 15:53
学习学习，积分到手
作者: zlyzlyzlyzly    时间: 2020-2-28 08:33
我是来学习的，，，，
作者: skyak47    时间: 2020-3-4 09:35
学习来了，虽然看不太懂
作者: wxhsff    时间: 2021-7-11 16:05
skyak47 发表于 2020-3-4 09:35
学习来了，虽然看不太懂

厉害科技刻录机林俊杰
作者: lsywinner    时间: 2022-1-3 19:24
果然学习室很难的
作者: 周新鹏    时间: 2022-1-30 02:33
谁能看懂呀
作者: 冷心923    时间: 2022-4-17 15:33
高.........
作者: laomailoveqq    时间: 2022-4-22 11:06
学习学习   完全看不懂
作者: binbin888    时间: 2022-5-10 14:43
完全看不懂
作者: 52梯控    时间: 2023-3-13 07:10
完全看不懂的来祖国学习
作者: jxy19871019    时间: 2023-7-21 16:04
路过，支持一下啦



欢迎光临 52梯控论坛 (https://52tikong.com/) Powered by Discuz! X3.4