[笔记]洗牌算法
如何实现随机性?
一个简单的题目:有一个大小为100的数组,里面的元素是从 1 到 100,怎样随机从里面选择 1 个数呢?
在Unity中的实现很简单:
public int GetRandomNum() |
注:在Unity中,Random.Range()
方法有两个不同的实现:
public static float Range(float min, float max);
包含min与max.
public static int Range(int min, int max);
不包含max,如果min与max相等,返回min。
不重复的50个数
题目难度增加:有一个大小为100的数组,里面的元素是从 1 到 100,怎样随机从里面选择不重复的50个数呢?。
如果我们随机50次也不能保证50个数字都是不重复的。
如果我们将随机的数放到数组里,去判断有没有这个数,是不是就可以解决了呢?有一说一,确实能完成题目要求,但是考虑极限就会发现越往后取数字,重复概率越高,需要重复随机的次数也就越多,我们在Unity中用取100个数来试一下:
Dictionary<int, int> Found = new Dictionary<int, int>(); |
输出前几个是这个样子的:
而后几个是这样的:
可以看到在最后几个数字的随机中,都重复了九十多次。越到最后一个,拿到没出现过的随机数越难,重复越多。
洗牌算法
我们可以对选出数的数组做点事情,让一个数出现在任意位置的概率事相同的。
Fisher–Yates Shuffle算法
思路是随机取索引值,每次从剩下的数字中随机取一个:
- 从还没处理的数组(假如还剩k个)中,随机产生一个[0, k]之间的数字p(假设数组从0开始);
- 从剩下的k个数中把第p个数取出;
- 重复步骤2和3直到数字全部取完;
- 从步骤3取出的数字序列便是一个打乱了的数列。
public void ShuffleFisherYates(int[] arr) |
这个算法开辟了一个新的空间用来复制数组。Random类是UnityEngine内的实现。
Knuth-Durstenfeld Shuffle算法
是Knuth和Durstenfeld在FIsher等人的基础上对算法进行了改进。
每次从未处理的数据中随机取出一个数组,然后把该数字放在数组的尾部,即数组尾部存放的是已经处理过的数字。这是一个原地算法。
public void ShuffleKnuthDurstenfeld(int[] arr) |
Random类是UnityEngine内的实现。
Inside-Out Algorithm
有些应用中可能需要保留原始数据,因此开辟一个新数组来存储打乱后的序列。
Inside-Out Algorithm 算法的基本思想是设一游标i从前向后扫描原始数据的拷贝,在[0, i]之间随机一个下标j,然后用位置j的元素替换掉位置i的数字,再用原始数据位置i的元素替换掉拷贝数据位置j的元素。其作用相当于在拷贝数据中交换i与j位置处的值。
public int[] ShuffleInsideOut(int[] arr) |
Random类是UnityEngine内的实现。
洗牌算法最佳实践
使用这个工具类即可:
这里用的是System里面的Random类,比较通用。
public static void Shuffle<T>(this IList<T> list) |