如何在 JavaScript 中對一個陣列進行隨機化或洗牌

Moataz Farid 2023年1月30日 2020年11月24日
  1. 根據 JavaScript 引擎對陣列進行洗牌
  2. 測量我們簡單演算法的隨機性
  3. 使用 Fisher-Yates Shuffle 演算法對一個陣列進行洗牌處理
  4. 使用 Underscore.jsLo-Dash 庫對一個陣列進行洗牌
如何在 JavaScript 中對一個陣列進行隨機化或洗牌

在本教程中,我們將學習如何在 JavaScript 中對一個陣列進行洗牌或隨機化處理;在 JavaScript 中洗牌陣列的方法有很多,不管是通過實現洗牌演算法還是使用一些庫中已有的洗牌函式。

洗牌陣列就是將其元素隨機排列,所以主要看你如何對陣列進行一定程度的重新排序或分類。

讓我們繼續前進,發現隨機化或洗牌一個陣列的不同方法。

根據 JavaScript 引擎對陣列進行洗牌

讓我們先實現一個簡單的陣列洗牌演算法,使用 array.sort() 對陣列進行排序,但使用 Math.random()-0.5 等式產生的一些隨機性,-0.5 確保每次呼叫演算法時,隨機值可以是正值或負值。

讓我們藉助 JavaScript 引擎的力量實現這個簡單的演算法,並使用 Console.log() 將洗牌後的 Array 列印到控制檯。

function shuffleArray(inputArray){
    inputArray.sort(()=> Math.random() - 0.5);
}

var demoArray = [1, 3, 5];
shuffleArray(demoArray);
console.log(demoArray);

輸出:

[1, 5, 3]

測量我們簡單演算法的隨機性

可以計算出該陣列的排列概率,以檢查我們實現的演算法有多優秀、多隨機。

我們來看看如何衡量它的隨機性。

  1. 建立一個字典,對所有的排列組合進行外觀統計。
  2. 建立一個迴圈,它將執行 1000000 次,每一次都將增加形成的排列組合的次數。
  3. 列印所有可能的排列組合的計數,觀察它們之間的概率。

這個簡單的測量演算法可以像下面這樣實現。

function shuffleArray(inputArray){
    inputArray.sort(()=> Math.random() - 0.5);
}

//counts of the appearances for all possible permutations
var countDic =  {
    '153': 0,
    '135': 0,
    '315': 0,
    '351': 0,
    '531': 0,
    '513': 0,  
};

//Creating the loop
for( var i = 0; i<1000000; i++){
    var arr = [ 1 , 5 , 3];
    shuffleArray(arr);
    countDic[arr.join('')]++;
}

//Print the counts of all possible permutations
for(var key in countDic){
    console.log(`${key}: ${countDic[key]}`);
}

輸出:

135: 62256
153: 375832
315: 62976
351: 311865
513: 124518
531: 62553

從上面的輸出中,我們可以清楚地看到偏差,因為 135315531 出現的次數比其他的少得多,所以彼此之間的計數相似。

使用 Fisher-Yates Shuffle 演算法對一個陣列進行洗牌處理

這種基於 JavaScript 引擎的簡單演算法在過去的部分中是不可靠的,但是一個叫做 Fisher-Yates 的偉大演算法就其效率和可靠性而言是更好的。

Fisher-Yates 演算法背後的思想是以相反的順序走到陣列,並將每個元素與前面的隨機元素交換。Fisher-Yates 是一個簡單但非常有效和快速的演算法。

讓我們來實現 Fisher-Yates 演算法。

function fisherYatesShuffle(arr){
    for(var i =arr.length-1 ; i>0 ;i--){
        var j = Math.floor( Math.random() * (i + 1) ); //random index
        [arr[i],arr[j]]=[arr[j],arr[i]]; // swap
    }
}

var tmpArray = [1, 3, 5];
fisherYatesShuffle(tmpArray);
console.log(tmpArray);

我們來一步步解釋一下吧

  1. for(var i =array.length-1 ; i>0 ;i--) 一個 for 迴圈,將在陣列上按相反的順序行走。
  2. Math.floor( Math.random() * (i + 1) ) 生成一個範圍在 0 和 i 之間的隨機指數。
  3. [arr[i],arr[j]]=[arr[j],arr[i]] 是用破壞性賦值語法將元素 arr[i]arr[j] 相互交換。

輸出:

(3) [3, 1, 5]

現在讓我們用之前的方法測試 Fisher -Yates

//counts of the appearances for all possible permutations
var countDic =  {
    '153': 0,
    '135': 0,
    '315': 0,
    '351': 0,
    '531': 0,
    '513': 0,  
};

//Creating the loop
for( var i = 0; i<1000000; i++){
    var arr = [ 1 , 5 , 3];
    fisherYatesShuffle(arr);
    countDic[arr.join('')]++;
}

//Print the counts of all possible permutations
for(var key in countDic){
    console.log(`${key}: ${countDic[key]}`);
}

輸出:

135: 166734
153: 166578
315: 166908
351: 166832
513: 166535
531: 166413

從上面的輸出,你可以看到 Fisher-Yates 演算法和我們之前實現的簡單演算法之間的巨大差異,以及 Fisher-Yates 演算法的可靠性。

使用 Underscore.jsLo-Dash 庫對一個陣列進行洗牌

著名的 Underscore.js 庫也提供了一個 shuffle 函式,可以直接隨機化一個陣列,而不需要你寫任何演算法的實現。

下面我們來看一下 _.shuffle() 方法的使用例項。

首先,我們需要在 HTML 模板裡面使用 Cloudflare CDN 匯入這個庫。

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.15/lodash.min.js"></script>

然後我們使用 _.shuffle() 方法,如。

var tmpUnderscoreArray = [1, 3, 5];
resultArray = _.shuffle(tmpUnderscoreArray);
console.log(resultArray);

輸出:

(3) [1, 5, 3]

相關文章 - JavaScript Array