[笔记]洗牌算法

如何实现随机性？

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

在Unity中的实现很简单：

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个数来试一下：

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);
    }
}

输出前几个是这个样子的：

而后几个是这样的：

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

洗牌算法

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

Fisher–Yates Shuffle算法

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

1. 从还没处理的数组（假如还剩k个）中，随机产生一个[0, k]之间的数字p（假设数组从0开始）；
2. 从剩下的k个数中把第p个数取出；
3. 重复步骤2和3直到数字全部取完；
4. 从步骤3取出的数字序列便是一个打乱了的数列。

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等人的基础上对算法进行了改进。

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

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位置处的值。

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类，比较通用。

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;
    }
}