如何实现随机性?

一个简单的题目:有一个大小为100的数组,里面的元素是从 1 到 100,怎样随机从里面选择 1 个数呢?

在Unity中的实现很简单:

1
2
3
4
public int GetRandomNum()
{
return Random.Range(1,101);
}

注:在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个数来试一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Dictionary<int, int> Found = new Dictionary<int, int>();
void Start()
{
while (Found.Count < 100)
{
int rNum = Random.Range(0, 101);
int time = 1;
while (Found.ContainsKey(rNum))
{
rNum = Random.Range(0, 101);
Debug.Log(Found.Count + ": Time:" + time);
time++;
}
Found.Add(rNum, rNum);
Debug.Log("Added: " + Found.Count);
}
}

输出前几个是这个样子的:
20200325165706
而后几个是这样的:
20200325165736

可以看到在最后几个数字的随机中,都重复了九十多次。越到最后一个,拿到没出现过的随机数越难,重复越多。

洗牌算法

我们可以对选出数的数组做点事情,让一个数出现在任意位置的概率事相同的。

Fisher–Yates Shuffle算法

思路是随机取索引值,每次从剩下的数字中随机取一个:

  1. 从还没处理的数组(假如还剩k个)中,随机产生一个[0, k]之间的数字p(假设数组从0开始);
  2. 从剩下的k个数中把第p个数取出;
  3. 重复步骤2和3直到数字全部取完;
  4. 从步骤3取出的数字序列便是一个打乱了的数列。
1
2
3
4
5
6
7
8
9
10
11
12
13
public void ShuffleFisherYates(int[] arr)
{
List<int> copy = new List<int>(arr);
int len = copy.Count;
while(len > 0)
{
int index = Random.Range(0, len);
int pick = copy[index];
copy.RemoveAt(index);
arr[len - 1] = pick;
len--;
}
}

这个算法开辟了一个新的空间用来复制数组。Random类是UnityEngine内的实现。

Knuth-Durstenfeld Shuffle算法

是Knuth和Durstenfeld在FIsher等人的基础上对算法进行了改进。

每次从未处理的数据中随机取出一个数组,然后把该数字放在数组的尾部,即数组尾部存放的是已经处理过的数字。这是一个原地算法。

1
2
3
4
5
6
7
8
9
10
public void ShuffleKnuthDurstenfeld(int[] arr)
{
for (int i = arr.Length - 1; i > 0; i--)
{
int index = Random.Range(0, i + 1);
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}

Random类是UnityEngine内的实现。

Inside-Out Algorithm

有些应用中可能需要保留原始数据,因此开辟一个新数组来存储打乱后的序列。

Inside-Out Algorithm 算法的基本思想是设一游标i从前向后扫描原始数据的拷贝,在[0, i]之间随机一个下标j,然后用位置j的元素替换掉位置i的数字,再用原始数据位置i的元素替换掉拷贝数据位置j的元素。其作用相当于在拷贝数据中交换i与j位置处的值。

1
2
3
4
5
6
7
8
9
10
11
public int[] ShuffleInsideOut(int[] arr)
{
List<int> res = new List<int>(arr);
for (int i = 0; i < arr.Length; i++)
{
int j = Random.Range(0, i);
res[i] = res[j];
res[j] = arr[i];
}
return res.ToArray();
}

Random类是UnityEngine内的实现。

洗牌算法最佳实践

使用这个工具类即可:

这里用的是System里面的Random类,比较通用。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void Shuffle<T>(this IList<T> list)
{
System.Random r = new System.Random();
int n = list.Count;
while(n>1)
{
n--;
int k = r.Next(n + 1);
T temp = list[k];
list[k] = list[n];
list[n] = temp;
}
}