Correctness of Fisher-Yates Shuffle Executed Backward

user_14147354 0
Viewed 230

According to wikipedia and also the implementation of Java standard library, shuffling https://en.wikipedia.org/wiki/Fisher–Yates_shuffle (Fisher Yates Shuffling) works like this:

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]

or equivalently

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]

My question is for the one below (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 and Algo B are just identical. But Algo C is different from Algo A and Algo B (in fact Algo C is Algo A executed in reverse direction)

Is Algo C correct? I am very confused. I did some chi-squared test using contingency table, and it appears that this gives apparently correct uniform order.

My question is whether Algo C is correct? If correct, why is it seen almost no where? Why F-Y shuffle is everywhere presented in one same direction.

probability shuffle pseudocode computer-science algorithm
2 Answers

Yes, this algorithm is correct, as it has a loop invariant that each permutation of the first i elements is equally likely. The invariant is initially satisfied when i = 1 because there is only one possible permutation of one element, and then when i = n (i.e. after the last iteration of the loop) each permutation of the whole array is equally likely.

To see why the invariant holds, we only need to consider a single iteration of the loop. Suppose the first i elements have all permutations equally likely, and we swap the first unshuffled element (call it x) with a random index up to or including itself. Now consider any two permutations P1 and P2 of the first i + 1 elements of the initial array: let Q1 and Q2 be the permutations of the first i elements which would result from swapping x in P1 and P2 respectively to index i. Since both Q1 and Q2 are equally likely by the inductive hypothesis, and both swaps are equally likely, and the only way P1 or P2 can happen is by these swaps starting from Q1 or Q2 respectively, it follows that P1 and P2 are equally likely to be the result.

So your algorithm is correct, but probably not well-known like Fisher–Yates because it has no advantages over Fisher–Yates, while being less obviously correct. Also worth noting is that it's easy to adapt Fisher–Yates to uniformly sample k < n distinct elements from the array in O(k) time, whereas your algorithm cannot be adapted in this way.

user_122990000

Focusing on why it isn't seen more (as the other answer already shows that it is correct).

The variants are useful as optimizations in various cases:

  • Algo B is useful if you only want a few of the random elements. Think shuffling a deck and handing out a few hands, and then collecting all the cards to reshuffle. With Algo B you don't have to shuffle the hands that weren't dealt.
  • Algo A is useful because you can skip the initialization, https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_%22inside-out%22_algorithm
  • Algo C would be useful if the collection isn't known in advanced, but this seems pretty esoteric. (So you randomly shuffle 5 cards, and then get a new one, take one more step, and then you have 6 shuffled cards etc.)

Those additional uses mean that Algo B and A will be coded more, and used even in other cases.

user_56032470
Related