2

As we know, Fisher–Yates shuffle give the following "modern algorithm" code:

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

My question is: if I change i in "i ≤ j < n" to 0, will the algorithm also be random as the algorithm above and how to prove? The modified code is:

  To shuffle an array a of n elements (indices 0..n-1):
  for i from 0 to n − 1 do
       j ← random integer with **0** ≤ j < n
       exchange a[j] and a[i]
Po Zhou
  • 595
  • 1
  • 5
  • 17
  • 3
    No, by opening up the rest the already shuffled part of the array to the random selection, skews the results. [this](http://datagenetics.com/blog/november42014/index.html) should explain it well. – Taekahn Mar 07 '15 at 08:32
  • You get a *random* shuffle, but it will be biased. The marked thread already discusses that question thoroughly. – amit Mar 07 '15 at 09:57
  • Someone marked your question as duplicate. However, I think the answers given to the other question concentrate on the distribution calculation, so I've added one additional answer [here.](http://stackoverflow.com/a/28936921/1016343) @Taekahn: Thank you for the excellent link, I enjoyed reading it! – Matt Mar 09 '15 at 07:53

0 Answers0