游戏常用算法-洗牌算法(代码片段)

关键词：

洗牌算法是一个比较常见的面试题。

一副扑克54张牌，有54!种排列方式。最佳的洗牌算法，应该能够等概率地生成这54!种结果中的一种

基于Unity的洗牌算法代码实现

GitHub链接

抽牌洗牌

原理

这是完全合乎现实洗牌逻辑的算法。

就是抽出纸牌的最后一张随机插入到牌库中，这般抽54次就完成了对扑克牌的洗牌

复杂度

空间O（1），时间O（n^2)

优缺点

如果牌库是以一个数组描述，这种插入式的洗牌不可避免地要大量移动元素。

Fisher_Yates算法

原理

取两个列表，一个是洗牌前的序列A1,2….54)，一个用来放洗牌后的序列B，B初始为空

while A不为空

随机从A取一张牌加入B末尾

复杂度

空间O（n），时间O（n^2)

代码实现

 1 List<int> list = new List<int>(pukes.pukes);//洗牌前的序列A
 2 List<int> newlist = new List<int>(list.Count);//洗牌后的序列B
 3 for(int i = 0 ; i < pukes.pukes.Length ; ++i)
 4 
 5 　　int randomIndex = Random.Range(0, list.Count);
 6 　　int r = list[randomIndex];//随机取牌
 7    newlist.Add(r);
 8    list.RemoveAt(randomIndex);
 9 
10 pukes.ResetPuke(newlist.ToArray());//序列B为洗牌后的结果

优缺点

算法原理清晰，但额外开辟了一个List，而且为List删除元素是不可避免地需要移动元素

通过54次生成的随机数取1/54,1/53,…1/1能等概率地生成这54!种结果中的一种

Knuth_Durstenfeld算法

Knuth 和Durstenfeld 在Fisher 等人的基础上对算法进行了改进。 每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部， 即数组尾部存放的是已经处理过的数字 。 这是一个原地打乱顺序的算法，算法时间复杂度也从Fisher算法的 O ( n 2 )提升到了 O ( n )。

1 for(int i = pukes.pukes.Length - 1;i>0;--i)
2   
3       int randomIndex = Random.Range(0, i+1);
4       pukes.Swap(randomIndex, i);
5   

是最佳的洗牌算法

Inside_Out算法

C++ stl中random_shuffle使用的就是这种算法

原理

在[0, i]之间随机一个下标j，然后用位置j的元素替换掉位置i的数字

通过54次生成的随机数取1/1,1/2,…1/54能等概率地生成这54!种结果中的一种

复杂度

空间O（1），时间O（n)

代码实现

1 public static void Shuffle(Pukes pukes)
2   
3       int len = pukes.pukes.Length;
4       for (int i = 0; i < len; ++i)
5       
6           int randomIndex = Random.Range(0, i + 1);
7           pukes.Swap(i, randomIndex);
8       
9   

random_shuffle

关于c++ stl 的random_shuffle

它的算法原理和Knuth_Durstenfeld类似

先从所有元素中选一个与位置1的元素交换，然后再从剩下的n-1个元素中选择一个放到位置2，以此类推

参考链接

维基百科-Fisher–Yates shuffle

markdown洗牌算法：数组随机排序(代码片段)

查看详情

javascriptfisher-yatesshuffle洗牌算法(代码片段)

查看详情

java偷懒洗牌算法(代码片段)

publicclassCardprivateStringcard;privateStringcolor;publicCard(Stringcard,Stringcolor)this.card=card;this.color=color;publicStringtoString()Stringss=color+":"+card+ 查看详情

关于洗牌算法的错误认识(代码片段)

下面是我之前一直使用的一个洗牌算法：letarr=[1,2,3,4,5,6,7,8,9];Array.prototype.shuffle=function()lettemp=this;for(leti=0;i<temp.length;i++)letindex=Math.floor(Math.random()*temp.length);letitemAtIndex=temp[index]; 查看详情

游戏概率游戏中的常见概率设计分析，游戏概率常用算法整理(代码片段)

...#x1f649;🎄学习专栏推荐：Unity系统学习专栏🌲游戏制作专栏推荐：游戏制作🌲Unity实战100例专栏推荐：Unity实战100例教程🏅欢迎点赞👍收藏⭐留言📝如有错误敬请指正！📆未来很长ÿ... 查看详情

游戏概率☀️游戏中的常见概率设计分析，游戏概率常用算法整理(代码片段)

...#x1f649;🎄学习专栏推荐：Unity系统学习专栏🌲游戏制作专栏推荐：游戏制作🌲Unity实战100例专栏推荐：Unity实战100例教程🏅欢迎点赞👍收藏⭐留言📝如有错误敬请指正！📆未来很长ÿ... 查看详情

随机洗牌算法knuthshuffle和错排公式(代码片段)

Knuth随机洗牌算法：譬如现在有54张牌，如何洗牌才能保证随机性。可以这么考虑，从最末尾一张牌开始洗，对于每一张牌，编号在该牌前面的牌中任意一张选一张和当前牌进行交换，直至洗到第一张牌为止。参考代码如下：voidk... 查看详情

洗牌算法(代码片段)

洗牌算法洗牌算法，刚在知乎这个回答上看到的一个算法，非常有趣。通过概率论的知识原地实现了一个公平的随机算法。大致的过程就是一个数组（假设有n个数），从后往前取第一个数A，第二个数随机从前面的数据中选取。... 查看详情

洗牌问题(代码片段)

...个洗牌程序，让随机取出一张牌的概率相同。要求：说明算法思路、分析时间复杂度、用Array编写洗牌程序、编写测试用例。算法思路时间复杂度??时间复杂度应该为：O(n）实现程序下面给出4种实现方法、比较各种方法的好坏，... 查看详情

洗牌算法(代码片段)

洗牌算法描述打乱一个数组。所以我们面临两个问题：1、什么叫做「真的乱」？2、设计怎样的算法来打乱数组才能做到「真的乱」？ 洗牌算法正确性的准则：产生的结果必须有n!种可能，否则就是错误的。**这个很好解释，... 查看详情

春节期间必学算法之-洗牌算法(代码片段)

春节期间免不了聚会，为了打发无聊的时间，免不了和亲朋好友一起打牌。想到这个问题，联想到如果亲朋好友让我这个程序员设计一个发牌的程序，我会怎么做呢？身为一名参加工作4年多的程序员的我，... 查看详情

程序员的算法趣题q50:完美洗牌(代码片段)

目录1.问题描述 2.解题分析2.1思路12.2思路23.代码及测试4.后记1.问题描述        问题：对2n张牌洗牌，并求当1<=n<=100时，一共有多少个n可以使得经过2(n-1)次洗牌后，恢复最初顺序？分两种情况考... 查看详情

洗牌算法c++将数组的元素顺序随机打乱(条件概率证明算法充分随机)(代码片段)

...一个数组内的元素随机打乱的需求，需要一个‘洗牌算法’，也就是需要生成数组下标的一个随机顺序。实现的思路如下（思路一比较复杂不好理解，推荐思路二）：以将一个元素个数为10的数组打乱为例&... 查看详情

fisher–yates-shuffle洗牌算法(代码片段)

functionshuffle(arr)vari=arr.length,t,j;while(i)j=Math.floor(Math.random()*i);i--;t=arr[i];arr[i]=arr[j];arr[j]=t;Math.floor(Math.random()*(m-n))+n;使用这个函数可以取得[n,m]之间的随机整数，包括n，不包括m  查看详情

洗牌算法

...e/details/6860339/扑克牌洗牌是我们生活中比较喜欢玩的一个游戏。那么我们有没有什么办法自己设计一个扑克牌洗牌的方法呢？在c运行库当中有一个随机函数rand，它可以生成0~32767之间的任意数。那么有没有可能利用这么... 查看详情

java实现洗牌算法(代码片段)

importjava.util.Iterator;importjava.util.LinkedList;importjava.util.List;importjava.util.Random;/**打乱扑克牌*/publicclasstest1 publicstaticvoidmain(String[]args) String[]hua=newString[]"黑桃","红桃","梅花","方砖"; String[]num="1","2... 查看详情

java实现洗牌算法(代码片段)

importjava.util.Iterator;importjava.util.LinkedList;importjava.util.List;importjava.util.Random;/**打乱扑克牌*/publicclasstest1 publicstaticvoidmain(String[]args) String[]hua=newString[]"黑桃","红桃","梅花","方砖"; String[]num="1","2... 查看详情

[384].打乱数组(代码片段)

[384].打乱数组题目算法设计：洗牌算法（Knuthshuffle算法）拒绝采样与洗牌算法的异同 题目输入["Solution","shuffle","reset","shuffle"][[[1,2,3]],[],[],[]]输出[null,[3,1,2],[1,2,3],[1,3,2]]解 查看详情