Fisher-Yates Shuffle 向后执行的正确性

Question

根据维基百科以及 Java 标准库的实施，洗牌 https://en.wikipedia.org/wiki/Fisher–Yates_shuffle (Fisher Yates Shuffling) 的工作原理如下：

算法 A：

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

或等同于

算法 B：

-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j]

我的问题是针对下面的问题（算法 C）：

算法 C：

-- To shuffle an array a of n elements (indices 0..n-1):
for i from 1 to n−1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[i] and a[j]

算法 A 和算法 B 完全相同。但是Algo C不同于Algo A和Algo B（其实Algo C是Algo A反方向执行）

算法 C 是否正确？我很困扰。我使用偶然性 table 做了一些卡方检验，看起来这给出了明显正确的统一顺序。

我的问题是算法 C 是否正确？如果正确，为什么几乎看不到它？为什么F-Y shuffle处处呈现同一个方向

Answer 1

是的，这个算法是正确的，因为它有一个 loop invariant，前 i 个元素的每个排列都是等可能的。当 i = 1 时最初满足不变量，因为一个元素只有一种可能的排列，然后当 i = n 时（即在循环的最后一次迭代之后）整个数组的每个排列都是同样可能的。

要了解为什么不变量成立，我们只需要考虑循环的单次迭代。假设第一个 i 元素的所有排列可能性均等，我们将第一个未打乱的元素（称为 x）与随机索引交换，直到或包括其自身。现在考虑初始数组的第一个 i + 1 元素的任意两个排列 P1 和 P2：让 Q1 和 Q2 是第一个 i 元素的排列，这将由交换 P1 中的 x 产生和 P2 分别索引 i。由于归纳假设 Q1 和 Q2 的可能性相同，并且两次交换的可能性相同，并且 P1 或 P2 发生的仅方式是分别从 Q1 或 Q2 开始的这些交换，因此 P1 和 P2 是结果的可能性相同。

所以你的算法是正确的，但可能不像 Fisher-Yates 那样广为人知，因为它与 Fisher-Yates 相比没有优势，而且不太明显是正确的。同样值得注意的是，很容易使 Fisher–Yates 在 O(k) 时间内从数组中统一采样 k < n 个不同的元素，而您的算法不能以这种方式进行调整。

Answer 2

关注为什么它没有被更多人看到（因为其他答案已经表明它是正确的）。

这些变体在各种情况下都可用作优化：

如果您只需要一些随机元素，算法 B 很有用。想想洗一副牌并分发几手牌，然后收集所有牌重新洗牌。使用算法 B，您无需洗牌未发牌的牌。
算法 A 很有用，因为您可以跳过初始化，https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_%22inside-out%22_algorithm
如果事先不知道该集合，Algo C 会很有用，但这看起来很深奥。（所以你随机洗了5张牌，然后得到一张新的，再走一步，然后你有6张洗牌等）

这些额外的用途意味着算法 B 和 A 将被更多地编码，甚至在其他情况下也会被使用。

Fisher-Yates Shuffle 向后执行的正确性

Correctness of Fisher-Yates Shuffle Executed Backward

algorithm

computer-science

probability

shuffle

pseudocode