随机问题之--洗牌算法
洗牌算法是我们常见的随机问题,在玩游戏、随机排序时经常会碰到。它可以抽象成这样:得到一个M以内的所有自然数的随机顺序数组。
在百度搜“洗牌算法”,第一个结果是《百度文库-洗牌算法》:http://wenku.baidu.com/view/c4fea82658fb770bf78a55b7.html
扫了一下里面的内容,很多内容都容易误导别人走上歧途,包括最后用链表代替数组,也只是一个有限的优化(链表也引入了读取效率的损失)。
该文里的第一种方法,可以简单描述成:随机抽牌,放在另一组;再次抽取,抽到空牌则重复抽。
“抽到空牌则重复抽”这会导致后面抽到空牌的机会越来越大,显然是不合理的。
可以优化一步成:牌抽走后,原牌变少。(而不是留下空牌)
代码如下:
function shuffle_pick_1(m) //洗牌 //抽牌法 { //生成m张牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //每次抽出一张牌,放在另一堆。因为要在数组里抽出元素,把后面的所有元素向前拉一位,所以很耗时。 var arr2 = new Array(); for (var i=m; i>0; i--) { var rnd = Math.floor(Math.random()*i); arr2.push(arr[rnd]); arr.splice(rnd,1); } return arr2; }
这个也明显有问题,因为数组如果很大的话,删除中间的某个元素,会导致后面的排队向前走一步,这是一个很耗时的动作。
回想一下“我们为什么要删除那个元素?”目的就是为了不产生空牌。
除了删除那个元素之外,我们是不是还有其它方式来去除空牌?
----有的,我们把最后一张未抽的牌放在那个抽走的位置上就可以了。
所以,这个思路我们可以优化成这样:
function shuffle_pick(m) //洗牌 //抽牌法优化牌 { //生成m张牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //每次抽出一张牌,放在另一堆。把最后一张未抽的牌放在空位子上。 var arr2 = new Array(); for (var i=m; i>0;) { var rnd = Math.floor(Math.random()*i); arr2.push(arr[rnd]); arr[rnd] = arr[--i]; } return arr2; }
除了抽牌思路,我们还可以用换牌思路。
《百度文库-洗牌算法》提到一种换牌思路:“随机交换两个位置,共交换n次,n越大,越接近随机”。
这个做法是不对的,就算n很大(例如10张牌,进行10次调换),也还存在很大可能“有的牌根本没换位置”。
顺着这个思路,做一点小调整就可以了:第i张与任意一张牌换位子,换完一轮即可。
代码如下:
function shuffle_swap(m) //洗牌 //换牌法 { //生成m张牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //第i张与任意一张牌换位子,换完一轮即可 for (var i=0; i<m; i++) { var rnd = Math.floor(Math.random()*(i+1)), temp = arr[rnd]; arr[rnd] = arr[i]; arr[i]=temp; } return arr; }
除了抽牌与换牌的思路,我们还可以用插牌的思路:先有一张牌,第二张牌有两个位置可随机插入(第一张牌前,或后),第三张牌有三个位置可随机插入(放在后面,或插在第一位,或插在第二位),依此类推
代码如下:
function shuffle_insert_1(m) //洗牌 //插牌法 { //每次生成一张最大的牌,插在随机的某张牌前。因为要在数组里插入元素,把后面的所有元素向后挤一位,所以很耗时。 var arr = [0]; for (var i=1; i<m; i++) { arr.splice(Math.floor(Math.random()*(i+1)),0,i); } return arr; }
以上的代码也会有一些问题:就是随着牌数的增多,插牌变得越来越困难,因为插牌会导致后面的很多牌都往后推一步。
当然,我们也可以适当的优化一下:先有n-1张牌,第n张牌放在最后,然后与任意一张牌互换位置。
代码如下:
function shuffle_insert(m) //洗牌 //插牌法优化版,可以用数学归纳法证明,这种洗牌是均匀的。 { //每次生成一张最大的牌,与随机的某张牌换位子 var arr = new Array(m); arr[0] = 0; for (var i=1; i<m; i++) { var rnd = Math.floor(Math.random()*(i+1)); arr[i] = arr[rnd]; arr[rnd] = i; } return arr; }
好的,全部的代码如下,有兴趣的同学可以在自己的机器上试下,看下他们各自的执行效率、以及最后的结果是否是理论随机。
<html> <head> <meta http-equiv="Content-Type" content="text/html; charset=gb2312"> <title>JK:javascript 洗牌算法 </title> </head> <body> <script type="text/javascript"> function shuffle_pick_1(m) //洗牌 //抽牌法 { //生成m张牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //每次抽出一张牌,放在另一堆。因为要在数组里抽出元素,把后面的所有元素向前拉一位,所以很耗时。 var arr2 = new Array(); for (var i=m; i>0; i--) { var rnd = Math.floor(Math.random()*i); arr2.push(arr[rnd]); arr.splice(rnd,1); } return arr2; } function shuffle_pick(m) //洗牌 //抽牌法优化牌 { //生成m张牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //每次抽出一张牌,放在另一堆。把最后一张未抽的牌放在空位子上。 var arr2 = new Array(); for (var i=m; i>0;) { var rnd = Math.floor(Math.random()*i); arr2.push(arr[rnd]); arr[rnd] = arr[--i]; } return arr2; } function shuffle_swap(m) //洗牌 //换牌法 { //生成m张牌 var arr = new Array(m); for (var i=0; i<m; i++) { arr[i] = i; } //第i张与任意一张牌换位子,换完一轮即可 for (var i=0; i<m; i++) { var rnd = Math.floor(Math.random()*(i+1)), temp = arr[rnd]; arr[rnd] = arr[i]; arr[i]=temp; } return arr; } function shuffle_insert_1(m) //洗牌 //插牌法 { //每次生成一张最大的牌,插在随机的某张牌前。因为要在数组里插入元素,把后面的所有元素向后挤一位,所以很耗时。 var arr = [0]; for (var i=1; i<m; i++) { arr.splice(Math.floor(Math.random()*(i+1)),0,i); } return arr; } function shuffle_insert(m) //洗牌 //插牌法优化版,可以用数学归纳法证明,这种洗牌是均匀的。 { //每次生成一张最大的牌,与随机的某张牌换位子 var arr = new Array(m); arr[0] = 0; for (var i=1; i<m; i++) { var rnd = Math.floor(Math.random()*(i+1)); arr[i] = arr[rnd]; arr[rnd] = i; } return arr; } //alert(shuffle_pick(10)) var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert], funcNames = ["抽牌", "抽牌优化", "换牌", "插牌", "插牌优化"] m = 10000, times=[]; for(var i = 0; i < funcs.length; i++){ var d0= new Date(); funcs[i](m); funcNames[i] = (new Date() - d0) + '\t' + funcNames[i]; } alert(funcNames.join('\n')); </script> </body> </html>
相关推荐
洗牌算法,整理了常用的洗牌算法,以及优劣比较,复杂度整理和概率等
该方案通过BioHashing方法得到用户指纹特征的二进制序列,对得到的序列执行一个改进的洗牌算法进行置乱,最后通过Fuzzy Vault方案将特征值与密钥进行绑定。仿真分析表明,利用Fuzzy Vault方案的容错机制和BCH码的...
描述了产生随机数算法的思路以及经典的洗牌算法,随机数和洗牌算法也是面试常见的题型
洗牌算法是我在面试过程中遇到的一个问题,我事后做了整理,与大家分享下思路,这个文档是我自己写的,如要转载,请注明出处。联系方式在文档里有说明。有什么想法或思路希望与我一起交流。
基于折叠技术的大数据样本洗牌算法研究.pdf
通过产生随机数进行交换,次数越多,越接近随机
有个长度为2n的数组{a1 a2 a3 an b1 b2 b3 bn} 希望排序后{a1 b1 a2 b2 an bn} 请考虑有无时间复杂度o n 空间复杂度0 1 的解法
VBS的洗牌算法 算法类资源 可以看看
斗地主算法类 适合初学者. 可以实现斗地主的洗牌发牌 无JFrame 简单易懂.
完美洗牌算法(解决微软面试题的论文)文章中给出了具体的算法思想
猜数游戏-----洗牌算法的典型应用 猜数游戏-----洗牌算法的典型应用
洗牌算法.md
洗牌算法 洗牌算法的核心思想是从最后一个元素开始,随机选择一个索引,然后交换当前元素和随机选择的元素。这个过程从最后一个元素一直持续到第一个元素。
功能介绍: 在一个规定的范围内生成指定数量不重复的随机数 理论基础: 基于基础的洗牌算法而设计出来的。当n无限接近于max时,即使max很大,时间复杂度能稳定在O(1)。
java的21点牌类游戏-自带洗牌算法与机器AI---【课程设计】 https://blog.csdn.net/dearmite/article/details/132301832#comments_28170675 本系列校训 用免费公开视频,卷飞培训班哈人!打死不报班,赚钱靠狠干! ...
C#洗牌算法,简单演示! 算法一、 /// /// 洗牌算法 /// private void test() { int[] iCards = new int[54]; for (int i = 0; i < iCards.Length; i++) { iCards[i] = i + 1; } // Random rand = new ...
php /** * 简单洗牌算法 */ $card_num=54; //牌数 print_r(wash_card($card_num)); function wash_card($card_num) { $cards=$tmp=array(); for($i=0;$i<$card_num;$i++){ $tmp[$i]=$i; } for($i=0;$i<$card...
基于折叠技术的大数据样本洗牌算法研究
先看最经典的 Fisher-Yates 的洗牌算法这里有一个该算法的可视化实现其算法思想就是 从原始数组中随机抽取一个新的元素到新数组中从还没处理的数组(假如还