一、说明

        Fisher-Yates洗牌算法是由 Ronald A.Fisher和Frank Yates于1938年发明的，后来被Knuth在书中介绍，很多人直接称Knuth洗牌算法， Knuth大家应该比较熟悉，《The Art of Computer Programming》作者，算法理论的创始人。

二、Fisher-Yates算法起源

2.1 Fisher-Yates算法起源

        1938 年，罗纳德·费舍尔 (Ronald Fisher) 和弗兰克·耶茨 (Frank Yates) 在他们的著作《生物、农业和医学研究的统计表》中描述了 Fisher-Yates 洗牌的原始形式。 [1]他们对算法的描述使用了铅笔和纸；随机数表提供了随机性。生成数字 1 到 N 的随机排列的基本方法如下：

        写下从 1 到 N 的数字。

• 在 1 和剩余的未击中数字的数量（含）之间选择一个随机数 k。
• 从低端数起，剔除第 k 个尚未剔除的数字，并将其写在单独列表的末尾。
• 从第 2 步开始重复，直到所有数字都被删除。
• 在第 3 步中写下的数字序列现在是原始数字的随机排列。
• 如果在上面的步骤 2 中选择的随机数是真正随机且无偏的，那么由此产生的排列也是如此。

        Fisher 和 Yates 仔细描述了如何以避免任何偏差的方式从提供的表格中获得任何所需范围内的此类随机数。他们还建议使用一种更简单的方法的可能性——从 1 到 N 中选择随机数并丢弃任何重复项——来生成排列的前半部分，并且仅将更复杂的算法应用于剩余的一半，其中选择一个重复的数字将否则变得令人沮丧地普遍。

2.2 问题归纳

• 假如给出一副扑克牌，如何用计算机模拟出一次洗牌？（每张牌等概率，每张牌不重复）。
• 训练集有一万组数据，从中随机选出3千组，不允许重复。

三、算法和实现

3.1 铅笔和纸上算法

        例如，我们将使用 Fisher 和 Yates 的原始方法将字母从 A 排列到 H。我们首先将字母写在一张草稿纸上，如下所示：

        现在我们从 1 到 8 滚动一个随机数 k——让我们把它设为 3——并在便签本上划掉第 k 个（即第三个）字母并将其记为结果：

        现在我们选择第二个随机数，这次是从 1 到 7：结果是 4。现在我们删除第四个尚未从草稿本删除的字母——即字母 E——并将其添加到结果中：

        现在我们从 1 到 6 中选择下一个随机数，然后从 1 到 5，依此类推，始终重复上述删除过程：

3.2 现代算法（计算机算法）

        我们现在将使用 Durstenfeld 的算法版本做同样的事情：这一次，我们不会删除所选字母并将它们复制到其他地方，而是将它们与最后一个尚未选择的字母交换。我们将像以前一样从 A 到 H 开始写出字母：    

        对于我们的第一次掷骰，我们掷出一个从 1 到 8 的随机数：这次是 6，所以我们交换列表中的第 6 个和第 8 个字母：

        我们从 1 滚动到 7 的下一个随机数，结果是 2。因此，我们交换第 2 个和第 7 个字母并继续：

        我们滚动的下一个随机数是从 1 到 6，恰好是 6，这意味着我们将列表中的第 6 个字母（在上面的交换之后，现在是字母 H）留在原处，然后移动到下一个步。同样，我们以相同的方式进行，直到排列完成：

        此时已经没有什么可以做的了，所以得到的排列是 G E D C A H B F。

 四、ptython案例

4.1 对任意序列实现洗牌效果

from random import randrange

def sattolo_cycle(items) -> None:
    """Sattolo's algorithm."""
    i = len(items)
    while i > 1:
        i = i - 1
        j = randrange(i)  # 0 <= j <= i-1
        items[j], items[i] = items[i], items[j]


lst = ["A","B","C","D","E","F","G","H"]
sattolo_cycle(lst)
print(lst)

五、后记

        此问题可以扩展成，从一个母体抽取一个样本。或者从集合抽取出一个子集的问题。大家看后自己尝试吧。