洗牌算法

Fisher-Yates 算法

​ Fisher-Yates Shuffle算法（又被称为 Knuth Shuffle 算法），是一种用于随机打乱元素顺序的高效洗牌算法。其保证生成的随机排列是等概率的。而且该算法是一种原地算法，对于大数据集场景也十分有效。该算法最初由Ronald Fisher、Frank Yates于1938年提出

算法原理

核心概括：从未知的数据中随机抽取一个数，排到已知序列的末尾，直到把未知数排满。

1. 对于一个长度为 size 的数据 arr，从第一个元素开始处理
2. 对当前正在处理的元素 arr[curIndex]，生成一个范围从 curIndex 到 size - 1 的随机数 ranVal
3. 将 arr[curIndex] 与 arr[ranVal] 位置对调
4. 重复以上步骤，直到 curIndex = size - 1 ，即到达序列末尾

算法思想 ---- “分区”

实际上是把整个数组进行了 分区 的操作：

1. 有序区（未操作区）：仍未处理过的元素的集合，即从 [curIndex, size-1]这个区间的元素池
2. 乱序区（已操作区）：已经经过乱序处理的元素序列

然后依次从有序区随机抽取一个数，放到乱序区的末尾，直到有序区元素只剩一个(没必要再排了）

算法特点----完全均匀分布

Fisher-Yates 算法生成的是完全均匀的随机分布

概率分布

对于一个包含 n 个元素的数组，存在 n! (n的阶乘) 种不同的排列组合。

Fisher-Yates 算法能保证每一种排列组合被生成的概率是完全相等的，即 $\frac{1}{n}$

计算

1. 处理最后一个位置时：算法会从全部 n 个元素中随机挑选一个放在最后。每个元素被选中的概率是 $1/n$。
2. 处理倒数第二个位置时：算法会从剩下的 n-1 个元素中随机挑选一个。每个元素被选中的概率是 $1/(n-1)$。
3. 以此类推，直到只剩最后一个元素，它被选中的概率是 $1/1$。

因此，要得到任何一个特定的排列顺序，其概率是所有这些独立选择概率的乘积：

$$P = \frac{1}{n} * \frac{1}{(n-1)} * ... * \frac{1}{2} * \frac{1}{1} = \frac{1}{n!}$$

证明了它的分布是完全均匀的。它被认为是“无偏的”，是生成随机排列的黄金标准。

代码实现

为直观展现，采用从后往前的排序方式：

从区间 0 到 i 作为有序区待选， i 到 数组末尾作为乱序区，每次处理位置 i 的元素，从有序区随机选取一元素与arr[i]交换 

在每一步 i，都确保了当前位置 i 的元素，是从所有尚未处理的元素（0 到 i）中等概率随机挑选出来的，这保证了最终所有 $n!$ 种排列是等概率的

JS实现：

function shuffArr(array:any[]){
    let shuffled = [...array];
    for(let i = shuffled.length - 1; i > 0 ;i--){
      const j = Math.floor(Math.random()*(i+1));//洗牌算法之Fisher-Yates Shuffle
      
      let a = shuffled[j];
      shuffled[j] = shuffled[i];
      shuffled[i] = a;
    }
    return shuffled;
  }

let listImgs = shuffArr(carouselImgsList);

• Math.random()：

  这是 JavaScript 的核心随机函数（实际上使用的线性乘余法或梅森旋转算法），它会生成一个大于等于 0，但严格小于 1 的浮点数（即小数）

• Math.floor：向下取整：高斯取整

• (i + 1)

  ​ 将 Math.random() 生成的 $[0, 1)$ 范围的数，乘以 (i + 1)，从而将范围扩大到$[0,i)$

Sattolo 算法

与 Fisher-Yates 区别

只生成构成 单个完整循环 的随机排列组合

核心思想

​ 数组的每一个元素在排列（不是排序，因为本身就是要把序列弄乱）后都不能位于原先未排列前的位置

例如 [a,b,c,d] ==> [d,c,a,b]，不能[a,d,b,c]

有三个人 [A, B, C] 参加抽签，规则是任何人都不能抽到自己。

算法特点 子集上均匀分布

Sattolo 算法不生成所有 $n!$ 种排列。它只生成那些被称为**“单循环排列”**的组合。对于 n 个元素，这样的单循环排列共有 $(n-1)!$ 种。

概率分布

Sattolo 算法能保证每一种单循环排列被生成的概率是完全相等的，即

$$\frac{1}{(n-1)!}$$

对于所有不是单循环排列的组合，Sattolo 算法生成它们的概率是 0。

代码实现

只需将

 const j = Math.floor(Math.random()*(i+1));

改为

 const j = Math.floor(Math.random()*(i));

即可