Data Structures Algorithms 简明教程
Fisher-Yates Shuffle Algorithm
Fisher-Yates 洗牌算法通过生成一个随机排列来对一个有限序列的元素进行洗牌。每个排列出现的可能性都是等可能的。该算法的方法是将序列的元素存储在袋子中，然后从袋子中随机抽取每个元素来形成洗牌后的序列。
算法以罗纳德·费雪和弗兰克·耶茨的名字命名，他们设计了洗牌的原始方法，该算法是无偏的。它在相同条件下生成所有排列，因此不会影响获得的输出。然而，Fisher-Yates 算法的现代版本比原始版本更有效率。
Fisher-Yates Algorithm
The Original Method
洗牌算法的原始方法使用笔和纸来生成有限序列的随机排列。生成随机排列的算法如下 −
Step 1 − 写下有限序列中的所有元素。声明一个单独的列表来存储获得的输出。
Step 2 − 在输入序列中随机选择一个元素 i 并将其添加到输出列表中。标记元素 i 为已访问。
Step 3 − 重复步骤 2，直到有限序列中的所有元素都已访问并随机添加到输出列表中。
Step 4 − 在处理完成后生成输出列表是生成的随机排列。
The Modern Algorithm
现代算法是对原始 Fisher-Yates 洗牌算法的稍加修改后的版本。修改的主要目的是通过减少原始方法的时间复杂度来实现原始算法的计算机化。现代方法由理查德·德斯滕菲尔德开发并由唐纳德·E·克努特推广。
因此，现代方法使用交换而不是维护另一个输出列表来存储生成的随机排列。时间复杂度降低到 O(n) 而不是 O(n2) 。算法如下所示 −
Step 1 − 在有限序列中写下元素 1 到 n。
Step 2 − 从输入序列中随机选择元素 i，并将其与列表中最后的未访问元素交换。
Step 3 − 重复步骤 2，直到已访问并交换有限序列中的所有元素。
Step 4 − 进程终止后生成列表是随机置换序列。
Pseudocode
在以下现代伪代码中，从最高索引到数组的最低索引执行 Shuffle。
Fisher-Yates Shuffle (array of n elements):
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]在以下现代伪代码中，从最低索引到数组的最高索引执行 Shuffle。
Fisher-Yates Shuffle (array of n elements):
for i from 0 to n−2 do
j ← random integer such that i ≤ j < n
exchange a[i] and a[j]Original Method Example
为了更好地描述算法，让我们对前六个字母的给定有限序列进行排列。输入序列：A B C D E F。
Step 1
这称为纸笔法。我们考虑一个存储有限序列的输入数组，和一个存储结果的输出数组。
Step 2
随机选择任何元素，并在标记其为已检查后，将其添加到输出列表中。在此情况下，我们选择元素 C。
Step 3
随机选择的下一个元素是 E，E 被标记并添加到已检查元素列表中。
Step 4
然后，随机函数选择下一个元素 A，并在标记其为已访问后将其添加到输出数组中。
Step 5
然后，从输入序列中剩余的元素中选择 F，并在标记其为已访问后将其添加到输出中。
Step 6
下一个被选择添加到随机排列的元素是 D。它被标记并添加到输出数组中。
Step 7
输入列表中存在的最后一个元素将是 B，因此最后它会被标记并添加到输出列表中。
Modern Method Example
为了降低原始方法的时间复杂度，引入了现代算法。现代方法使用交换来对序列进行 Shuffle - 例如，该算法的作用类似于通过交换原始卡组中卡牌的位置来 Shuffle 一副牌。我们来看一个示例，以了解 Fisher-Yates 算法的现代版本是如何工作的。
Step 1
首先将字母作为输入，并使用现代方法对它们进行 Shuffle。
Step 2
随机选择元素 D，并将其与序列中最后一个未标记的元素（在本例中为 F）交换。
Step 3
对于下一步，我们选择元素 B 与最后一个未标记的元素“E”交换，因为 F 已在之前的步骤中被换到 D 的位置。
Step 4
我们接下来将元素 A 与 F 交换，因为 F 是列表中的最后一个未标记的元素。
Step 5
然后，将元素 F 与最后一个未标记的元素 C 交换。
Step 6
序列中剩下的元素最后可以交换，但是由于随机函数选择了 E 作为元素，它被保留原样。
第 7 步
保留剩下的元素 C，不交换。
交换后得到的数组是最终输出数组。