什么是JavaScript中的Fisher-Yates随机播放?

Fisher-Yates随机算法

该算法将对数组中的元素进行混洗。要随机播放数组中的元素,我们可以编写自己的逻辑,但是许多开发人员认为F isher-Yates现代随机播放算法是随机播放数组中的元素的最佳方法。该算法具有以下步骤。

遵循的步骤

  • 根据此算法,我们应该从后到前循环数组。例如,在下面的示例中,我们有一个数组,该数组由索引0到索引7的8个元素(A,B,C,D,E,F,G,H)组成。因此,第一次循环将影响元素最后一个索引7是H。

  • 下一步是在所选索引7和索引0之间生成一个随机数(随机索引)。假设让随机索引为3。

  • 获得随机索引交换后,所选索引中和随机索引处的元素。所提供数组中随机索引处的元素为D。因此,交换后,该数组将更改为A,B,C,H, E,G,F,D。 

  • 在第二个循环中,只需忽略最后一个索引(因为它已经循环了),并尝试在元素A和F之间找到索引0和索引6之间的随机索引。令生成的随机索引为2。

  • 获取随机索引后,让我们在索引6和2处交换元素。现在,数组将看起来为A,B,F,H,E,G,C,D。

  • 该算法遵循相同的模式,即它忽略索引6,并开始在索引5和索引0之间寻找随机索引,依此类推,直到到达索引1。它不能使索引0循环,因为没有索引小于0。用于交换目的。

  • 注意,有可能将生成的随机索引选择为循环索引。例如,让循环在选定的索引4和索引0之间运行。让生成的随机索引为4。然后索引4的值将保持在同一位置。

以下示例说明了Fisher-Yates现代随机播放算法

示例

<html>
<body>
<script>
   var arr = ['A','B','C','D','E','F','G','H']
   var i = arr.length, k , temp;      // k is to generate random index and temp is to swap the values
   while(--i > 0){
      k = Math.floor(Math.random() * (i+1));
      temp = arr[k];
      arr[k] = arr[i];
      arr[i] = temp;
   }
   document.write(arr);
</script>
</body>
</html>

输出结果

C,F,H,D,A,G,E,B  // note that output will change for every iteration.