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