根据维基百科以及Java标准库的实现，shufflinghttps://en.wikipedia.org/wiki/Fisher–Yates_shuffle(Fisher Yates Shuffling(的工作原理如下：
Algo 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]
或等效
Algo 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]
我的问题是下面的一个(Algo C(：
Algo 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]
Algo A和Algo B完全相同。但是Algo C不同于Algo A和Algo B(事实上Algo C是反向执行的Algo A(
Algo C正确吗？我很困惑。我用列联表做了一些卡方检验，似乎这给出了明显正确的统一顺序。
我的问题是Algo C是否正确？如果是正确的，为什么在哪里几乎看不到？为什么F-Y洗牌无处不在，呈现在同一个方向。
关注为什么它没有被更多地看到(因为另一个答案已经表明它是正确的(。
这些变体在各种情况下都是有用的优化：
- 如果您只想要一些随机元素，Algo B是有用的。想象一下洗牌，分发几张牌，然后收集所有的牌进行洗牌。有了阿尔戈B，你就不必洗牌了
- Algo A很有用，因为您可以跳过初始化，https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_%22inside-输出%22_算法
- 如果这个集合还不为人所知，Algo C会很有用，但这似乎很深奥。(所以你随机洗牌5张，然后得到一张新牌，再多走一步，然后你就有6张洗牌的牌等(
这些额外的使用意味着Algo B和A将被更多地编码，甚至在其他情况下也会被使用。
是的，这个算法是正确的，因为它有一个循环不变量，即第一个i元素的每个排列的可能性相等。不变量最初在i = 1时被满足，因为一个元素只有一个可能的排列，然后在i = n时(即在循环的最后一次迭代之后(，整个阵列的每个排列都是同样可能的。
要了解为什么不变量成立，我们只需要考虑循环的一次迭代。假设第一个i元素具有相同可能性的所有排列，并且我们将第一个未屏蔽的元素(称为x(与直到或包括其自身的随机索引进行交换。现在考虑初始阵列的第一i + 1元素的任意两个排列P1和P2：设Q1和Q2是第一i元素的排列，其将分别从P1和P2中的x交换到索引i。由于根据归纳假设，Q1和Q2的可能性相等，并且这两种交换的可能性也相等，并且P1或P2发生的唯一方式是分别从Q1或Q2开始进行这些交换，因此P1和P2的可能性相等。
所以你的算法是正确的，但可能不像Fisher–Yates那样广为人知，因为它比Fisher–Yats没有优势，但不太明显正确。同样值得注意的是，很容易调整Fisher–Yates以在O(k(时间内从阵列中均匀采样k < n不同元素，而您的算法不能以这种方式进行调整。