萨托洛算法(2017)

Sattolo的算法I最近遇到了一个问题，解决方案的一部分是执行一系列指针访问，这些访问将以伪随机顺序遍历一大块内存。Sattolo的算法为此提供了解决方案，因为它只产生一个周期的列表排列，这保证了即使我们以随机顺序遍历列表中的每个元素，我们也能找到它。

然而，我可以在网上找到的关于算法工作原因的解释要么使用了某种数学机制(Stirling数字，假设熟悉循环记法等)，要么使用了我很难理解的逻辑。我发现这在解释那些可以但不必使用大量数学机器的概念时是很常见的。我不认为使用现有的数学方法本身有什么错--如果你熟悉这些概念，这是一个很好的思维捷径。如果你正在上一门组合学课程，如果你熟悉斯特林数，那么涵盖斯特林数，然后快速说出一系列证明是微不足道的结果是有意义的，但对于只对一个结果感兴趣的人来说，我认为不幸的是，很难找到一个不需要任何背景的相对简单的解释。当我在寻找一个简单的解释时，我还发现很多人在不合适的地方使用萨托洛的算法，还有一些人不知道萨托洛的算法就是他们想要的，所以这里我们尝试解释一下为什么该算法不适用于大学本科的组合学背景。

在我们看Sattolo的算法之前，让我们先看看Fisher-Yates，这是一种产生数组/向量的随机排列的就地算法，其中每种可能的排列都以均匀的概率出现。

我们将看看Fisher-Yates的代码，然后看看如何证明算法产生了预期的结果。

对于范围(n-1)内的i，def Shuffle(A)：n=len(A)：#i从0到n-2，包括0和n-2。J=从i到n-1的随机随机范围(i，n)#j(包括i和n-1在内)。A[i]，a[j]=a[j]，a[i]#交换a[i]和a[j]。

随机选取一个数组并产生该数组的排列，即，它对该数组进行随机排列。我们可以将这个循环看作是将数组的每个元素a依次从a[0]放到a[n-2]。在一些迭代中，i，我们从n-i个元素中选择一个与之交换，并将元素i与某个随机元素交换。数组中的最后一个元素a[n-1]将被跳过，因为它将始终与自身交换。要想看到这会以均匀的概率产生所有可能的排列，一种方法是写下每个元素最终出现在任何特定位置的概率1。另一种方法是观察有关此算法的两个事实：

Fisher-Yates产生与排列一样多的输出(每个输出都是一个排列)。

(1)对于我们在算法中做出的每个随机选择，如果我们做出不同的选择，我们会得到不同的输出。例如，如果我们查看结果a[0]，将原来位于a[k](对于某个k)中的元素放入结果a[0]中的唯一方法是用迭代0中的[k]替换a[0]。如果我们选择一个不同的元素进行交换，我们最终会得到一个不同的结果a[0]。一旦我们放置a[0]并查看结果a[1]，同样的事情也适用于a[1]，对于每个a[i]依此类推。此外，每个选项都将范围缩小相同的量--这是一种对称，因为虽然我们将[0]放在第一位，但我们可以将任何其他元素放在第一位；每个选择都有相同的效果。这隐约类似于您可以通过统一随机选取数字(一次选取一个数字)来均匀随机选取整数的原因。

(2)费舍尔-叶茨生产了多少种不同的产出？在第一次迭代中，我们为a[0]确定n个可能的选择之一，然后给定该选择，为a[1]确定n-1个选择之一，然后为a[2]确定n-2个选择之一，依此类推，因此有n*(n-1)*(n-2)*...2*1=n！可能的不同输出。

按照几乎相同的推理，这与n个元素的可能排列的数量完全相同。如果我们想要计算n个元素的可能排列的数量，我们首先从n个可能的元素中选择第一个位置的一个，第二个位置选择n-1个，依此类推，结果是n！可能的排列。

由于Fisher-Yates只产生唯一的排列，并且有和排列一样多的输出，所以Fisher-Yates产生每一种可能的排列。由于Fisher-Yates以均匀概率产生每个输出，所以它以均匀概率产生所有可能的排列。

现在，让我们来看看Sattolo的算法，它与Fisher-Yates几乎完全相同，也产生了一个混洗版本的输入，但产生了一些完全不同的东西：

Def sattolo(A)：n=len(A)，i在范围(n-1)内：J=随机随机范围(i+1，n)#i+1而不是i a[i]，a[j]=a[j]，a[i]。

我们不像在Fisher-Yates中那样随机选择要交换的元素，而是随机选择一个不是要放置的元素的元素，也就是说，我们不允许元素与其自身交换。这样做的一个副作用是没有元素在最初开始的地方结束。

在我们讨论为什么这会产生预期的结果之前，让我们确保我们在术语上是一致的。查看数组的一种方法是将其视为图的描述，其中索引指示节点，值指示边指向的位置。例如，如果我们有列表0 2 3 1，可以认为这是一个从索引到值的有向图，它是一个具有以下边的图：

节点0指向自身(因为索引0处的值是0)，节点1指向节点2(因为索引1处的值是2)，依此类推。如果我们遍历这张图，我们会看到有两个圈。0->；0->；0...。和1->；2->；3->；1....

让我们假设我们将位置0的元素与其他元素交换。它可以是任何元素，但假设我们将其与位置2中的元素交换。然后，我们将获得列表3 2 0 1，可以将其视为下图：

如果我们遍历此图，我们会看到循环0->；3->；1->；2->；0....。这是一个恰好只有一个周期的排列的例子。

如果我们交换属于不同周期的两个元素，我们将把这两个周期合并成一个周期。要了解这一点，一种方法是当我们交换列表中的两个元素时，我们实质上是拿起指向每个元素的箭头，并交换它们所指向的位置(而不是保持不变的箭头尾巴)。跟踪这一结果就像跟踪数字8一样。例如，如果我们用另一个循环的任意元素交换0，假设元素2，我们将得到3 2 0 1，其唯一的循环是0-&>3-&>1-&>2->；0……。请注意，此操作是可逆的--如果我们再次进行相同的交换，最终将再次出现两个周期。通常，如果我们交换同一周期中的两个元素，则将该周期分为两个单独的周期。

如果我们输入一个由0 1 2组成的列表...。N-1到Sattolo的算法，我们将得到恰好一个周期的排列。此外，我们有相同的概率产生恰好有一个循环的任何排列。让我们来看看为什么Sattolo‘s只产生一个周期。然后，我们将弄清楚为什么它以均匀的概率产生所有可能的循环。

对于萨托洛的算法，让我们假设我们从列表0 1 2 3开始…。N-1，即长度为1的n个循环的列表。在每次迭代中，我们进行一次交换。如果我们从两个独立的循环中交换元素，我们将合并这两个循环，将循环数减少1。然后，我们将进行n-1次迭代，将循环数从n减少到n-(n-1)=1。

现在，让我们来看看为什么假设我们总是交换来自不同周期的元素是安全的。在算法的每一次迭代中，我们将具有索引>；i的一些元素与索引i处的元素交换，然后递增i。由于i被递增，所以放入索引i中的元素永远不能再次交换，也就是说，每次交换将交换的两个元素中的一个放到其最终位置，即对于每个交换，我们获取两个可能可交换的元素，并将其中一个元素呈现为不可交换。

当我们开始时，我们有n个长度为1的循环，每个循环都有一个可交换的元素。当我们用某个随机元素交换初始元素时，我们将获取其中一个可交换元素并使其不可交换，从而创建一个长度为2的具有1个可交换元素的循环，并留下n-2个其他循环，每个循环有1个可交换元素。

维护的关键不变量是每个周期恰好有一个可交换元素。当我们有n个长度为1的循环时，不变量在开始时有效。只要这是真的，每次我们合并任意长度的两个循环时，我们将从一个循环中取出可交换元素，并将其与另一个循环中的可交换元素交换，从而使两个元素中的一个不可交换，并创建一个更长的周期，它仍然只有一个可交换元素，从而保持不变量。

因为我们不能交换同一周期中的两个元素，所以我们在每次交换时合并两个周期，每次迭代减少1个周期，直到我们已经运行了n-1次迭代并且恰好只剩下一个周期。

要查看我们以相等的概率生成每个周期，请注意，只有一种方法可以生成每个输出，即，更改任何特定的随机选择都会导致不同的输出。在第一次迭代中，我们随机选择n-1个放置，然后是n-2，然后是n-3，依此类推，因此对于任何特定的循环，我们以概率(n-1)*(n-2)*(n-3)...*2*1=(n-1)！如果我们能证明有(n-1)个！正好有一个循环的排列，那么我们就会知道我们生成的每个排列都是以均匀的概率恰好有一个循环的。

假设我们有一个长度为n的任意列表，它正好有一个周期，我们添加单个元素，有n种方法可以将其扩展为长度为n+1的周期，因为我们可以在新元素中添加n个位置并保留该周期，这意味着长度为n+1的周期(n+1)的数量为n*个周期(N)。

例如，假设我们有一个循环，它产生路径0->；1->；2->；0...。我们想要添加一个新元素3。我们可以用->；3->；替换任何->；，并获得长度为4的循环，而不是长度为3的循环。

在基本情况下，有一个长度为2的循环，排列1 0(另一个长度为2的排列，0 1，有两个长度为1的循环，而不是长度为2的循环)，因此我们知道Cycle(2)=1。如果我们应用上面的递归，我们得到Cycle(N)=(n-1)！，这正好是Sattolo算法生成的不同排列的数目，这意味着我们用一个循环生成所有可能的排列。因为我们知道我们以均匀的概率生成每个循环，所以我们现在知道我们以均匀的概率生成所有可能的单圈排列。

另一种方法是查看有(n-1)个！正好有一个循环的排列，就是我们旋转每个循环，使0在开始处，并将其记为0->；i->；j->；k->；……。这些元素的数量与0->；右侧元素的排列数量相同，即(n-1)！。

我们已经看过两种完全相同的算法，除了两个字符的改变。这些算法产生完全不同的结果--一种算法产生随机排列，另一种算法产生恰好只有一个周期的随机排列。我认为这些算法很简洁，因为它们非常简单，只是一个带交换的双for循环。

在实践中，您可能不需要知道这些算法是如何工作的，因为大多数现代语言的标准库都会以某种方式产生随机洗牌。如果你有一个可以让你洗牌的函数，如果你不介意一种需要额外传递的非就地算法，你可以用恰好一个周期产生一个排列。我会把它留给读者作为练习，但是如果你想要一个提示，有一种方法可以与另一种方法类似，它可以看到有`(n-1)！恰好只有一个循环的排列。

虽然我说过你可能不需要知道这些东西，但是如果你要实现一个定制的洗牌算法，你确实需要知道它！这听起来可能很明显，但人们实施不正确的洗牌算法的历史由来已久。这在90年代甚至21世纪初的游戏和在线博彩网站中很常见，你仍然可以看到偶尔出现的错误实现的洗牌，例如，当微软实现了虚假的洗牌，并且未能正确地随机进行浏览器选择投票。当时，谷歌在javascript随机数组排序方面最热门的是微软最终使用的不正确算法。该站点已经修复，但您仍然可以在网上找到不正确的教程。

没有元素以其原始位置结束的排列称为错位。当我搜索Sattolo算法的用法时，我发现很多人使用Sattolo算法来生成随机排列。虽然Sattolo算法生成的是乱排，但它只生成恰好一个循环的乱排，而且存在多于一个循环的乱排(例如，3210)，所以它不可能产生概率均匀的随机乱排。

生成随机乱排的一种方法是使用Fisher-Yates生成随机洗牌，然后重试，直到我们得到乱排为止：

定义乱排(N)：断言n！=1，"；不能有长度为1的乱排；a=list(range(N))而不是is_disangement(A)：Shuffle(A)返回a。

这个算法很简单，并且极有可能最终返回一个错位(对于n！=1)，但是在返回结果之前我们应该期望它运行多长时间并不是很明显。也许我们在第一次尝试就会出现混乱，然后运行一次洗牌，或者可能需要尝试100次，然后我们必须进行100次洗牌，然后才会出现混乱。

要弄清楚这一点，我们需要知道随机排列(洗牌)是错位排列的概率。为了得到这一点，我们想知道，给定一个长度为n的列表，有多少排列，有多少错位。

因为我们在附录中讲得很深入，所以我假设您知道n个元素的排列数是n！二项式系数是什么，用泰勒级数就行了。

为了计算排列错位的数目，我们可以从排列的数目n！开始，然后从元素保持在其起始位置的排列中减去(n选择1)*(n-1)！。这是不太正确的，因为这双减法会将两个元素保留在起始位置的排列相加，所以我们必须加回(N Choose 2)*(n-2)！。这是不太正确的，因为我们用三个排列过度校正了元素，所以我们必须重新添加这些元素，依此类推，结果是∑(−1)ᵏ(N Choose K)(n−k)！。如果我们将其展开并除以n！并将其抵消，我们得到∑(−(1)ᵏ(1/k！)。如果我们看极限，当元素的数量达到无穷大时，这看起来就像e^x的泰勒级数，其中x=-1，即1/e，也就是说，在极限中，我们预计错位排列的分数是1/e，也就是说，我们期望产生错位排列的交换次数是产生随机排列的e倍。像许多交替的级数一样，这个级数收敛得很快。当k=10时，e的有效位数在7位以内！

我们的算法的一个愚蠢之处在于，如果我们将第一个元素放在第一个位置，我们已经知道我们没有错位，但是我们会继续放置元素，直到我们创建了一个完整的排列。如果我们拒绝非法安置，我们甚至可以做得比e管理费用的因素更好。也有可能想出一个基于非拒绝的算法，但我真的很喜欢基于朴素拒绝的算法，因为我发现，当由基本随机算法组成的基本随机算法不断尝试时，它会很好地发挥作用。

我写这个解释是因为我发现维基百科上的解释比较难理解，但是如果你觉得上面的解释很难理解，也许你会更喜欢维基百科的版本：

事实上，萨托洛的算法总是产生一个长度为n的循环，这可以通过归纳法来证明。通过归纳假设，在循环的初始迭代之后，剩余的迭代根据长度为n-1的循环排列前n-1个元素(那些剩余的迭代只是应用于前n-1个元素的Sattolo算法)。这意味着将初始元素跟踪到其新位置p，然后将最初位于位置p的元素跟踪到其新位置，依此类推，只有在访问了所有其他位置之后才能返回到初始位置。假设初始迭代将最后一个元素与(非最终)位置k处的元素交换，并且前n-1个元素的后续排列然后将其移动到位置l；我们将所有n个元素的排列π与前n-1个元素的剩余排列σ进行比较。如上所述，跟踪连续的位置，在到达位置k之前，σ和π之间没有区别。但是，在π下，原来位于位置k的元素被移动到最终位置，而不是移动到位置l，并且原来位于最终位置的元素被移动到位置l。此后，π的位置序列再次遵循σ的序列，并且根据需要，在返回初始位置之前将访问所有位置。

对于等概率的排列，只要观察到改进的算法涉及(n-1)！产生不同可能的随机数序列，每个序列明显产生不同的排列，并且假设随机数源是无偏的，每个序列都以相等的概率发生。(n-1)！这样产生的不同排列恰好耗尽了长度为n的一组循环：每个这样的循环都有一个唯一的循环记数法，其值n在最终位置，这允许(n-1)！对剩余值进行排列，以填充循环记数法的其他位置。

感谢Mathieu Guay-Paquet、Leah Hanson、Rudi Chen、Kamal Marhubi、Michael Robert Arntzenius、Heath Borders、Shreevatsa R和David Turner的意见/更正/讨论。

在循环的第一次迭代上放置一个[0]。假设RANDRANGE在适当的范围内以均匀的概率生成整数，则原始a[0]与任何元素(包括其自身)交换的概率为1/n，因此得到的a[0]有1/n的机会是原始a中的任何元素，这正是我们想要的。

在循环的第二次迭代上放置一个[1]。此时，[0]是数组中变异前的某个元素。让我们将未变异的数组称为原始数组。对于某个k，A[0]是原始的[k]。对于任何特定的k值，它都包含概率为1/n的原始的[k]。然后我们用范围[1，n-1]中的某个元素交换a[1]。

如果我们想要计算出[1]是来自原始的某个特定元素的概率，我们可以这样认为：对于某个k，A[0]是原始的[k_0

.