Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >如何优雅地给扑克牌排序?(二)——排序算法的一次工程实践

如何优雅地给扑克牌排序?(二)——排序算法的一次工程实践

作者头像
magic2728
发布于 2019-09-27 06:26:06
发布于 2019-09-27 06:26:06
9590
举报
文章被收录于专栏:MatheMagicianMatheMagician

在上一篇文章中,我们一起探讨了排序类问题的数学本质,其问题的真实适用范围以及由此定义下能够证明有效的两类排序算法流程,分析了他们的适用范围和时间,空间上的复杂度边界,让我们对这类问题有了全面的认识。

那今天我们要探讨的,如何给一副完全洗乱的扑克牌仅用双手排序的问题(不允许借助桌面等类似内存作用的地方),可以看作是学好了科学,划定了边界以后的一次工程实践。

如果以上算是一次小型的科学研究思考,那么转化为技术,还需要一些工程的实践,我们以“把计算机科学的排序算法迁移到人给扑克牌排序”这个问题为例来说明,看你能不能体会出科学和工程的区别,以及分别的妙处。

这个问题很有意思,首先,科学上最好的快排和归并其实都不怎么好,你想想每次都要突出来一张牌标明左右分别大于或者小于它,或者归并的序列估计要摆满一桌子,这有多麻烦。而这些操作在计算机上不过是递归罢了,不过是不断地把数据压入栈顶再一股脑倒出来,对应的是CFG(上下文无关文法)的解析器,即LBA(线性有界自动机)。而且实际运行过程的每一步对计算机来说都及其高效而不会出错。

看到了吧,我们面临的问题非常棘手,我们的双手单位操作时间远远长于计算机,而且递归几十层人类也会疯掉,直接套用在计算机科学理想条件下最优的方式来让人执行并发挥不出优势,况且我们也就需要处理52张牌而已。

于是拿起扑克牌端详了起来,有这么几点想法:

1. 人的双手要想迅速完成批量操作,摆一桌子是不现实的,需要找到人能批量完成的操作;

2. 其实,完整的一副扑克牌是范围给定且连续无间断的,这样看起来比一般任意集合排序容易,因为明确知道2后面是3,而不用担心中间还需要插入什么,即每个元素都有有精确的桶,或者叫槽位;

3. 扑克牌的点数有两位数表达,低位是13进制的,高位是4进制的,这个天然可以用基数排序,再利用桶获得接近线性的复杂度;

4. 对于3~5张牌,尤其是还相邻的牌,人类不需要什么章法也能迅速的排序,换句话说,如果我们能够先粗排,再精排,像快排那样分块,或者阶梯分班那样培养,或是搜索排序那样先效率高地简单算一把以后再精排,是一个不错的办法;

5. 判断一张牌是否是某点数范围,是否是某花色比要比较任意两张牌要快,比较同花色/同数字的两张牌大小也比任意比较要快很多;

好了,这一切都有前辈们思考过了,魔术师们凭借着对自己双手和大脑的直觉,设计出了一些方案来做出这些酷炫的效果,上期我们已经提到,这期我们先回顾一下:这个方法是John Hamman发表在他的大作《The Secrets of Brother John Hamman》中的,并一直流传着,请看视频:

视频1 John Hamman Sorting Cards

可以看到,整个过程一共进行了4词Cull操作和一次微调,其具体流程为:

1. Cull 1, 2, 3, 7, 8, 9到底部;

2. Cull 4, 5, 6, 1, 2, 3到底部;

3. Cull红色的牌到底部;

4. Cull梅花和红心到底部;

5. 微调顺序;

在这个流程里,我上面提到的几点想法在这个作品中也完全体现出来了:

1. Cull是一个隐秘而又可以快速批量进行的魔术手法,还考验魔术师的手法功底,而一次Cull等价于一次二分桶的hash!

2. 用到的就是基数排序,对于13进制的A-K的低位,我们用两次二分桶完成了1-3, 4-6, 7-9, 10-K的该位上的粗排,神奇的是,这个粗排性质在高位排序后不会受到影响!这恰是基数排序 背后的数学原理保证的!随后,对4进制的花色位再次进行了二次而分桶,这样花色位的排序就完全完成了;

3. 最后仅剩下3-4张同花色,仅数字不同,还连号,知道具体范围的位置微调,遍历一遍即可完成;

经过噼里啪啦一顿操作,方才混乱的扑克牌居然恢复了顺序!简直是奇迹!

再一次体现了,魔术师真的是带着镣铐跳舞,用最简单的手法操作,用计算机的思维,组合出绝妙的效果。

还没完,无论是数学家,还是魔术师,亦或是我们数学魔术师,最赖以生存的品质就是精益求精,钻研到底。到目前为止,我们学习了John Hamman在处理“扑克牌人工快速排序”时候留下的经验,并且经过思考剖析,理解了这么设计的原理,包括计算机复杂度分析的方法以及在特定条件下如何用工程思维调整地策略。这些分析也许发明者自己都没意识到,也许是他太聪明,意识流里想出来的方法,但是我们学习者,一定要探究其原理,才能为己所用,不然就只是傻乎乎追星了。

好了,到了学习成长最关键的一步了,既然已经站在了巨人的肩膀,并且站稳了,不妨再向上跳一步:John Hamman的方法设计从原理上讲还有没有改进的空间,哪些部分还不是最优的?

显然,这个方案的弊病其实也很明显,那就是4次的Cull操作其实非常刺眼,实地考察实验会发现,这个方法虽然像个谦谦君子般优雅,但是比一些直觉化的,没有什么章法铺满一地的方案快不了多少,真是乱拳打死老师傅啊。老师傅一定要在智慧上碾压后辈,才能被年轻人尊敬啊。

为什么需要4次Cull呢,那是因为两个进制位,等效四进制的每位需要两次二桶hash才能够完成,能不能够把桶数直接改到4个,使得这个hash过程一次性完成呢,这样就只需要两次操作了,答案是可以的!请看视频!

视频2 Quaternary sorting Cards Method

Cull的手法天然是一个二分桶,利用的是扑克序列可以依据两个竖直方向起点位而分开,而这个方向到3都很困难,因为会找不到插入口。但是,横向方向还没有使用啊,如果把这两个组合起来,恰好完成了两个二分桶达到四进制位的完全排序效果,所需的基本排序次数直接减半!

有了这个想法以后,最开始发现要hold住4个序列的Cull有点困难,其实有一点手法基础和牌感,一点不难的,关键是,它的效果很让人激动人心啊,直接把4次Cull缩减为2次,几乎达到时间减半的效果,这简直是算法和人手的天作之合!邓爷爷说的对啊,科学技术是第一生产力啊!科学给予指导,技术在生产环境下实践出效果来,做的是提高量级的事情啊!怎么不让人激动!

而最后的微调方式上也可以有一些微优化,我经过一些测试,感觉对于人类来说,直接观察初始顺序,按照插入排序方案逐个找到值从小到大的牌即可,或者因为这是个已知完全集合,哪些牌是确定的,可以相当于构造无冲突hash,总之熟练以后,可以迅速微调得到最后解。

有同学可能会提问了,你这个方法也不见得多快啊?为什么一开始我们要限定不使用桌面呢?有桌面的话,就我们往常经验,把不同抽出来花色排成四叠,再一叠一叠地摊开按照数字抽取排序,甚至轻而易举可以超过上面所谓设计精妙的方案啊!

其实你没有想错,我们如果借助桌面,开扇出来hash出花色和找到点数排序,这相当于是每个时刻,眼睛都可以同时并行搜索到多张同花色以及多张相邻的值的牌,虽然手上功夫是串行的,但是瓶颈一定在眼睛的查找速度上,因为手的速度几乎就是发一遍扑克牌的速度。所以当我们可以在计算机上有并行资源的时候,总是可以在数量级上实现效率的飞跃。如果扑克牌排序也这样做,那也是极好的。

比如,对于快排和归并排序,其在可否并行时的递归表达式为:

所以,就比较排序而言,有并行资源时候,还能再把速度提高一个log数量级,但是,完全并行是理想的,还需要考虑到计算机或者人的资源量等实际因素,在扑克牌排序问题上,显然是有显著提高的,并行而灵活地查找以及排序是人乃以生存的远超机器的能力,但是可以想见,如果扑克牌的张数更多到几百几千张,这些小把戏都都在海量的条件下失效了。要清楚地明白,计算机复杂度是在变量趋于无穷时候的性质,但是实际工程问题并不会无穷,故要灵活对待和处理。

从计算机基于比较和非比较的排序算法,到特定环境下的一次排序实战,我们体会了计算机科学的美,给我们划定了一条边界和方法论的指导;另外,在实际环境中在给定条件和要求范围内解决问题也是我们看重的能力,是作为一个工程师的必备素养。相信你在凭借兴趣开心地学习的过程中,能够领悟这些道理,迅速地成长。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-03-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 MatheMagician 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
如何优雅地给扑克牌排序?(一)——排序算法的数学本质
不知平常各位打牌时候是否遇到过这样的场景:四人打完升级后,面对两幅混乱的扑克牌,走了一人后想打斗地主,现在要把他们分出一副来,于是打算先排序后分离,然后各种花色,数字,摆满一桌子,乱成一团,等排好了,5分钟过去了……
magic2728
2019/09/27
2K0
如何优雅地给扑克牌排序?(一)——排序算法的数学本质
对称、群论与魔术(五)——真实扑克牌图案的对称性探索
前面的系列文章我们聊过了如何用群来描述对称性。而在上一篇中,我们着重讲了扑克牌从一个D4的空白正方形,演化成一个C2的印着背面对称图案的过程中不同阶段的对称情况,相关内容请戳:
magic2728
2022/05/18
1.6K0
对称、群论与魔术(五)——真实扑克牌图案的对称性探索
De Bruijin序列与魔术(一)——De Bruijin序列简介
在牌序领域,一个特别数学化也是很冷门的一个序,DeBruijin序列,算是经典中的经典了。但它在魔术圈里流传并不甚广的原因是,可扩展性不强,学习记忆相对也困难,即魔术表演价值的性价比不是很高。但是作为一一对应函数,通信编码的经典结构,其数学价值仍然很高,魔术价值也可以继续挖掘。作为数学魔术师,我们还是应当奉为圭臬,好好品读,学习一番。
magic2728
2023/08/09
5240
De Bruijin序列与魔术(一)——De Bruijin序列简介
对称、群论与魔术(六)——经典魔术《对称找牌》
在前面的文章中,我们聊完了对称性的呈现和群论描述,以及从简单到复杂的在扑克牌上,对称性的具体分析,相关内容请戳:
magic2728
2022/05/18
4170
对称、群论与魔术(六)——经典魔术《对称找牌》
八大排序算法的Java实现(下)
2)通过一趟排序讲待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
JavaEdge
2021/02/23
6650
八大排序算法的Java实现(下)
八大排序算法详解_面试+提升
八大排序算法详解_面试+提升 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大
Java帮帮
2018/03/15
1.4K0
八大排序算法详解_面试+提升
我和Double Lift的故事(五)——升华篇​
本来这个系列写到第二篇时,写完了我学习各种Double Lift的使用方法的进步以及应用的逻辑以后,基本上也就江郎才尽了。不料最近灵感突发,决定狗尾续貂一波,再度升华一把这个扑克手法的经典。十多年的打磨和思考,总是能够不经意中给我一些意想不到的收获。
magic2728
2020/02/17
5340
破解魔术的秘密(三)——逻辑推理在《三叠感应》魔术中的应用
在前面的文章中,我们直面魔术秘密并提出了使用逻辑推理方法破解秘密的步骤,相关内容请戳:
magic2728
2023/01/30
3850
序列周期性与魔术(二)——扑克牌叠里的周期性
其中,我们谈到一叠扑克牌在位置平移操作下的数学结构是最基础的群——循环群(Cyclic Group),记作Cn,n即为我们的周期:
magic2728
2020/06/04
8460
Si Stebbins Stack中的数学与魔术(六)——魔术《周而复始的世界》
在本系列前面的4篇作品中,我们从数学和实际操作角度对Si Stebbins Stack的各种性质作了全面的介绍,上一篇讲到了其第一个经典应用《恐怖透视术》,相关内容请回顾:
magic2728
2021/04/02
6240
文字对称中的数学与魔术(八)——魔术《抓牌奇迹》与系列总结
今天我们介绍本系列最后一个作品,堪称压轴大戏。要知道,前面的作品都是基于常规的语言文字,和横着写的正常文字序列来的,那别的符号世界有没有对称的字符,竖着写的文字又如何?
magic2728
2023/03/06
4330
文字对称中的数学与魔术(八)——魔术《抓牌奇迹》与系列总结
加加减减的奥秘——从数学到魔术的思考(三)
我们已经从数学原理的发现到扑克牌魔术的映射过程分别做了详细的分析。相信大家对这个加减互为逆运算的原理以及设计成魔术的基本方案都略有了解。上一篇中我们也特意提到了扑克魔术中的两个基本手法:Dealing和Cut,且主要就Dealing手法进行了数学到魔术的创作,其中不少创意大家应该还觉得有所收获吧!那么,今天最后一篇,我们来讨论下Cut手法下,我们如何利用好这个加减逆运算的原理来设计精品。
magic2728
2019/09/27
4480
文字对称中的数学与魔术(四)——魔术《3 or 8》
在前面的文章里,我们介绍了语言文字的对称性,包括阿拉伯数字,英语和汉语。其对称性主要是图形中最基础的轴对称和中心对称,以及抽象序列的回文对称,相关内容请戳:
magic2728
2023/03/06
4490
文字对称中的数学与魔术(四)——魔术《3 or 8》
关于洗牌的研究(七)——从数学到魔术之鸽尾洗牌
写再前面:本系列作品由MathMagician独家首发,一共有七篇,从数学和魔术两个角度对日常生活中“洗牌”这一现象作了挂一漏万的分析。之所以说是挂一漏万,是因为无论数学还是魔术,洗牌中的任何一个小点都够写几篇了。所以,本系列主要选取了一些常见的洗牌方式和相关内容展开作了一些介绍,包括洗牌分类,混乱度评价,过程建模,近似计算,以及几个基本但是及其巧妙的利用洗牌规律设计的魔术。相信聪明的你读完以后,会在数学和魔术上,都对“洗牌”这一现象有着更加深入的认识。
magic2728
2019/09/27
1K0
De Bruijin序列与魔术(二)——魔术《De Bruijin序列》
上一篇我们介绍了De Bruijin序列的基本数学内容以及其如何应用在魔术上的一些基本内容,今天我们就来学习一下这个经典的《De Bruijin序列》魔术。
magic2728
2023/09/09
3050
De Bruijin序列与魔术(二)——魔术《De Bruijin序列》
神奇的德布鲁因序列
数学中存在这样一个序列,它充满魔力,在实际工程中也有一部分的应用。今天就打算分享一下这个序列,它在 Google S2 中是如何使用的以及它在图论中,其他领域中的应用。这个序列就是德布鲁因序列 De Bruijn。
一缕殇流化隐半边冰霜
2018/08/30
2.6K0
神奇的德布鲁因序列
八大排序算法
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/hguisu/article/details/7776068
用户2965768
2019/06/20
7730
八大排序算法
魔术《4 Kings 折纸》的三重境界(四)——魔术效果的突破
就像数学总是走在所有科学的前沿,因为思绪飞扬的速度一定是最快的。那在数学魔术里,我们也可尝试一把用理论来倒推魔术效果的实验。
magic2728
2023/11/22
1670
魔术《4 Kings 折纸》的三重境界(四)——魔术效果的突破
关于洗牌的研究(六)——从数学到魔术之完美洗牌
写再前面:本系列作品由MathMagician独家首发,一共有七篇,从数学和魔术两个角度对日常生活中“洗牌”这一现象作了挂一漏万的分析。之所以说是挂一漏万,是因为无论数学还是魔术,洗牌中的任何一个小点都够写几篇了。所以,本系列主要选取了一些常见的洗牌方式和相关内容展开作了一些介绍,包括洗牌分类,混乱度评价,过程建模,近似计算,以及几个基本但是及其巧妙的利用洗牌规律设计的魔术。相信聪明的你读完以后,会在数学和魔术上,都对“洗牌”这一现象有着更加深入的认识。
magic2728
2019/09/27
1.4K0
Si Stebbins Stack中的数学与魔术(九)——序列的多重周期性
在前面的文章中,我们依次介绍了好几个难度不一,各有特色的基于Si Stebbins Stack设计的魔术,相关内容请戳:
magic2728
2021/05/11
4450
Si Stebbins Stack中的数学与魔术(九)——序列的多重周期性
推荐阅读
相关推荐
如何优雅地给扑克牌排序?(一)——排序算法的数学本质
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档