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

Question

根据维基百科和Java标准库的实现，shuffling 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 是否正确？我很迷茫。我使用列联表做了一些卡方检验，这似乎给出了明显正确的统一顺序。

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

Answer 1

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

变体在各种情况下可用作优化:

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

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