算法笔记(二)抽牌法产生随机全排列
上一章的算法笔记,并不算一个算法系列的一个合适的開始。而本章将会介绍一种产生随机全排列的方法,下一章開始,就正式開始我们的排序算法了。
在我们的排序算法演示器中,我们须要一组随机的数据来作为排序的開始,而本章,就会产生这么一组随机数据。
(一)实现分析
我们须要一组随机的数据,并且似乎产生的方法不会太难。我们仅仅须要通过rand()函数获得一个随机数,让其对count(排序的规模)取模,结果作为数组的索引,其值是当前已产生的随机数的个数,假设已经存在了,继续查找,直到产生随机数的个数与总数同样。
这样的方法的最大问题在于,我们须要产生的是一组全排列,当排序的规模较大时,最后几个数字的命中率低的可怕,这样的方法仅仅能被抛弃。
说到全排列,似乎另一种方法,我们能够通过标准库中的一个算法,next_permutation(),依次得到全排列,那么我们能够先有序排列,然后获得n次下一个全排列,n为一个随机数,它从0到全排列的种类。问题又来了,全排列种类怎么算的?阶乘,太可怕了,这个种类的总数在达到一定规模的时候,不见得会比上面一种方法快。这样的方法也被pass。
然后就是我们今天要使用的方法了,抽牌法。首先声明哈,这样的方法,是我从某杂志上看来的,并不是全然原创。
我们可以想想生活中发牌的实例,我们经过一轮洗牌发牌之后,似乎仅仅须要一遍就行搞定了,并且根本不可能存在未命中的情况。它是怎么实现的呢?首先随机抽出一张牌,将其从牌堆中取出,再从剩下的牌堆中,再随机抽出一张....以此类推。
(二)构建模型
事实上从上面的说法,模型已经非常明显了。我们须要一个牌盒来放还剩下的牌,须要还有一个牌盒,来放入取出的牌。依次从剩下的牌中随机抽出一张牌,直到最后没有剩下牌为止。
1. 创建两个数组,我们能够使用vector,也能够通过动态分配,给int型指针分配count个整数。
2. 然后利用rand()函数,从中抽出一个数来,将其存入还有一个数组中。
3. 剩余牌盒中将被抽到的这个数字和剩余牌盒中最后一个数字交换,下次仅仅从前count-1个数中抽取,下一次反复2中的操作,直到剩余数组中个数为0。
4. 假设使用了指针,做些清理工作。
(三)代码实现
这段代码,临时就不写了,相信熟练掌握不论什么一种语言的程序猿都可以依照上述方法以o(n)的效率产生全排列随机数了吧。
好了,从下篇博客中,我们就要開始排序啦,各种各样排序算法,将会通过我们的演示程序一一展示出来,想起来又略有点小兴奋。
相关文章
- 【万字专栏总结】离线强化学习(OfflineRL)总结(原理、数据集、算法、复杂性分析、超参数调优等)
- 算法刷题笔记02:Linked List
- 算法刷题笔记01:Array
- 【笔记】《游戏编程算法与技巧》7-12
- 【笔记】《游戏编程算法与技巧》1-6
- 垃圾回收算法学习
- 视频编解码算法面试总结
- Netty权威指南_算法笔记上机指南pdf
- 算法笔记汇总精简版下载_算法与数据结构笔记
- 认知算法(二)
- 决策树算法的应用python实现_python怎么画出决策树的分支
- 【算法竞赛 - 数据结构】加权并查集的理解(以POJ1703为例)
- 外网疯传!字节大佬闭关三月撰写的数据结构与算法笔记遭恶意开源
- 《算法竞赛进阶指南》0x17 二叉堆
- 感知哈希算法计算图像相似度
- 《斯坦福算法博弈论二十讲》学习笔记(持续更新)
- 基本算法:逆转链表
- AI好奇心,不只害死猫!MIT强化学习新算法,智能体这回「难易通吃」
- 二叉树——堆的排序 TOP-K算法
- 【伯克利博士论文】网络优化算法及其在分子生物学中的应用
- Java数据结构学习笔记之二Java数据结构与算法之栈(Stack)实现详解编程语言
- 算法-二叉树的镜像详解编程语言