Fisher-Yates Shuffle算法

1.創(chuàng)建一個新的list
2.隨機取出當前0-list.Count其中一個數
3.把老list當前隨機數位置添加到新list
4.老list刪除這個數
5.直到老list.Count=0結束返回

    public void FisherYatesShuffle<T>(List<T> list)
    {
        List<T> cache = new List<T>();
        int currentIndex;
        while (list.Count > 0)
        {
            currentIndex = Random.Range(0, list.Count);
            cache.Add(list[currentIndex]);
            list.RemoveAt(currentIndex);
        }
        for (int i = 0; i < cache.Count; i++)
        {
            list.Add(cache[i]);
        }       
    }

隨機性 可驗證每一個數的概率都是相等的

一個元素m被放入第i個位置的概率P = 前i-1個位置選擇元素時沒有選中m的概率 * 第i個位置選中m的概率

image.png

時間復雜度為O（n^2）空間復雜度為O（n）

Knuth-Durstenfeld Shuffle算法

是上面板的升級版本 不用new新的list 在原list進行交換
1.隨機取出當前0-list.Count-i的數(就是相當于不移除，要從后每次遍歷都要從后往前空出一個位置給隨機完的數交換到（最后一個-i）這個位置)
比如一共1234
你在前四個隨機一個2 2和4交換 成了1432
然后在前三個隨機 只能隨機到143其中一個
就按3來說 他和自己交換就是位置不變 成了1432
然后在前兩個交換 比如隨機了一個1 和4交換 成了4132
最后一個不交換不然會數組越界
2.把當前隨機的數和最后空出來的數交換
這樣可以確保不會重復隨機

   public void KnuthDurstenfeldShuffle<T>(List<T> list)
    {
        //隨機交換
        int currentIndex;
        T tempValue;
        for (int i = 0; i < list.Count; i++)
        {
            currentIndex = Random.Range(0, list.Count - i);
            tempValue = list[currentIndex];
            list[currentIndex] = list[list.Count - 1 - i];
            list[list.Count - 1 - i] = tempValue;
        }
    }

然后用forr優(yōu)化 因為for循環(huán)每次都獲取list.count比較 而forr是反向 只用獲取一次
不過有局限因為只有開始獲取了長度而不是每次獲取 導致必須一開始知道長度 長度未知的話只能用第一種

    public void KnuthDurstenfeldShuffle<T>(List<T> list)
    {
        //隨機交換
        int currentIndex;
        T tempValue;      
        for (int i = list.Count - 1; i >= 0; i--)
        {
            currentIndex = Random.Range(0, i+1);
            tempValue = list[currentIndex];
            list[currentIndex] = list[i];
            list[i] = tempValue;
        }
    }

隨機性

image.png

也是相等的
時間復雜度為O（n）空間復雜度為O（1）
是最佳的洗牌算法

Inside-Out Algorithm算法

上面算法是內部打亂算法 如果我們想保留數據需要另外開辟一個List保存 我覺得跟上面的差不多就用個list保存 數組是struct可以直接賦值時間復雜度可能是O(n)

public List<T> InsideOutAlgorithm<T>(List<T> list)
    {
        List<T> cache = new List<T>();
        for (int i = 0; i < list.Count; i++)
        {
            cache.Add(list[i]);
        }
        //隨機交換
        int currentIndex;
        T tempValue;
        for (int i = cache.Count - 1; i >= 0; i--)
        {
            currentIndex = Random.Range(0, i + 1);
            tempValue = cache[currentIndex];
            cache[currentIndex] = cache[i];
            cache[i] = tempValue;
        }
   
        return cache;
    }

時間復雜度為O（n^2）空間復雜度為O（n）

ReservoirSampling蓄水池抽樣算法

如果我們想從一個從N個元素中隨機的抽取k個元素，其中N無法確定 就要用到這個算法
其實還有一種算法一開始會想到等概率抽取法，每次在（0，n-1）隨機一個數，隨機m次如果有相同的重新隨機。如果N較大也可能不確定大小就只能用蓄水池抽樣了
1.先把讀到的前k個對象放入“水庫”
2.對于第k+1個對象開始，以k/(k+1)的概率選擇該對象，以k/(k+2)的概率選擇第k+2個對象，以此類推，以k/m的概率選擇第m個對象（m>k）。
3.如果m被選中，則隨機替換水庫中的一個對象。最終每個對象被選中的概率均為k/n，證明如下。

第m個對象被選中的概率=選擇m的概率（其后元素不被選擇的概率+其后元素被選擇的概率不替換第m個對象的概率）

image.png

  public List<T> ReservoirSampling<T>(List<T> list, int m)
    {
        List<T> cache = new List<T>(m);
        for (int i = 0; i < m; i++)
        {
            cache.Add(list[i]);
        }
        int currentIndex;
        for (int i = m; i < list.Count; i++)
        {
            currentIndex = Random.Range(0, i + 1);
            if (currentIndex < m)
            {
                 cache[currentIndex] = list[i];
            }
        }
        return cache;
    }