samedi 7 mars 2015

Will the modified "Fisher–Yates shuffle" implementation remain random?

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 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]




Aucun commentaire:

Enregistrer un commentaire