什么是 JavaScript 中的 Fisher-Yates 洗牌算法？

给定一个数组，生成数组元素的随机排列。这类似于洗牌或随机化一个数组，并且洗牌后每次的结果都应该相同且等概率出现。

输入输出场景

假设一个数组包含一些元素，并且我们对该数组进行了 Fisher-Yates 洗牌。输出数组将被随机洗牌，每次执行都会进行不同的洗牌。所有排列都是等概率的。

Input = [2, 4, 6, 8, 10] 
Output = 4, 10, 6, 2, 8 // first iteration 
         8, 10, 2, 6, 4 // second iteration 
         2, 10, 8, 6, 4 // third iteration

考虑一个 arr[] 数组。一种更简单的解决方法是创建一个最初是 arr[] 数组副本的 temp[] 数组。从 temp[] 中随机选择一个元素，并将此元素复制到 arr[0]，然后删除 temp[] 中的元素。重复此过程，直到从 temp[] 中随机选择每个元素并将其移动到 arr[]。

算法

该算法反复执行将数组中随机选择的元素与数组中最后一个元素交换的操作。

以下是洗牌数组的步骤：

  • 在给定数组的第一个索引和最后一个索引之间选择一个随机索引号。

  • 现在，将该元素与最后一个索引元素交换。

  • 重复步骤一，但将该元素排除在选择之外。

  • 当随机选择中只剩下第一个索引时，停止洗牌。

  • 每次都重复步骤一，并且前一次随机选择的最后一个索引应从选择中排除。

以下是 Fisher-Yates 数组洗牌的工作原理：

为了了解 Fisher-Yates 数组洗牌的工作原理，让我们假设一个数组 arr=[10, 20, 30, 40, 50]。

  • 从第一个索引 arr[0] 和最后一个索引位置 arr[4] 中，随机选择 30 并交换 30 和 50。


  • 从第一个索引 arr[0] 和最后一个索引位置 arr[3]（排除之前的选择）。

  • 随机选择 20 并交换 20 和 40。


  • 从第一个索引 arr[0] 到最后一个索引位置 arr[2]（排除之前的选择）。

  • 随机选择 30，不会发生交换，因为随机选择的索引不在 arr[0] 和 arr[2] 之间。


  • 从第一个索引 arr[0] 到最后一个索引位置 arr[1]（排除之前的选择）。

  • 随机选择 10 并交换 10 和 40。


  • 洗牌后的最终数组如下面的图片所示。(此处应插入图片)


示例 1

在下面的示例中，我们创建了一个包含元素的数组。还创建了一个 while 循环，只要数组长度大于 0，循环就会运行。

每次 while 循环重复时，Array.length 都会递减 1，并且一旦交换，最后一个索引就会从循环中删除。

元素将在 temp 和 i 之间交换。当 while 循环迭代所有可能性时，它将打印输出。每次再次运行程序时，输出都会有所不同。

<!DOCTYPE html>
<html>
   <title>Fisher-Yates shuffle in JavaScript</title>
<head>
   <button onClick = "fisher_yates()"> Fisher Yates</button>
   <p id = "para"></p>
   <script>
      function fisher_yates(){
         let array = [40, 90, 50, 70, 80, 30, 60, 10, 20];
         let i = array.length;
         while (--i > 0) {
            let temp = Math.floor(Math.random() * (i + 1));
            [array[temp], array[i]] = [array[i], array[temp]];
         }
         document.getElementById("para").innerHTML = array;
      };
   </script>
</head>
<body>
</body>
</html>

示例 2

在下面的示例中，我们创建了一个包含元素的数组。还创建了一个 for 循环，只要数组长度大于 0，循环就会运行。

数组长度每次 for 循环重复时都会递减 1，并且一旦交换，最后一个索引就会从循环中删除。

我们还创建了一个按钮并在其中传递了 fy() 函数。每当单击按钮时，循环就会再次开始运行，并且每次单击时都会打印洗牌后的数组。

<!DOCTYPE html> 
<html> 
<body> 
   <button onclick="fy()">Try Fisher-Yates</button> 
   <p id="para"></p> 
   <script> 
      let Array = [25,1,5,10,40,100]; 
      let len = Array.length; 
      let x; 
      function fy() { 
         for (x = len -1; x > 0; x--) { 
            var y = Math.floor(Math.random() * x) 
            var temp = Array[x] 
            Array[x] = Array[y] 
            Array[y] = temp 
         } 
         document.getElementById("para").innerHTML = Array; 
      }; 
   </script> 
</body> 
</html>

更新于：2022年9月23日

5000+ 次浏览

启动您的 职业生涯

通过完成课程获得认证

开始学习
广告