mercredi 30 mars 2016

Shuffle: Why is a for loop switching arr[i] with arr[r] (r : random 0 - length - 1) not a uniformly random shuffle?

I am currently taking Sedgewick's algorithms course on Coursera (taught in java). He says to create a uniformly random shuffling algorithm, I must go through each index i in my array, swapping that element with a random element FROM ONLY THOSE ELEMENTS I'VE ALREADY LOOKED OVER. He says if I were to swap the element with a random element out of the entire array, it wouldn't be uniformly random. Please explain why not? If for every iteration element[i] is swapped at complete random with another element in the array, including itself, than 1/N is always the probability of where element[i] will end up; I don't see how bias is introduced.

in other words he advocates :

for (var i = 0; i < arr.length; i++){
  var r = Math.floor(Math.random() * i + 1)
  swap(r, i);
}

over

for (var i = 0; i < arr.length; i++){
  var r = Math.floor(Math.random() * arr.length)
  swap(r, i);
}

Excuse the JavaScript as I am a brand new programmer and am more comfortable with it. Also please let me know if I have any fundamental misunderstandings with regards to how random numbers work, thank you :)




Aucun commentaire:

Enregistrer un commentaire