vendredi 20 mars 2015

Random Shuffling in Java (or any language) Probabilities

So, I'm watching Robert Sedgewick's videos on Coursera and I am currently at the Shuffling one. He's showing a "poorly written" shuffling code for online poker (it has a few other bugs, which I've removed because they are not related to my question) This is how the algorithm works:



for(int i = 0; i < N; i++)
int r = new Random().nextInt(53);
swap(cardArray, i, r);


It iterates all the cards once. At each iteration a random number is generated and the i-th card is swapped with the r-th card. Simple, right?


While I understand the algorithm, I didn't understand his probability calculation. He said that because Random uses a 32-bit seed (or 64, it doesn't seem to matter), this is constrained to only 2^32 different permutations.


He also said that Knuth's algorithm is better (same for loop, but choose a number between 1 and i) because it gives you N! permutations.


I can agree with Knuth's algorithm calculations. But I think that on the first one (which is supposed to be the faulty one) there should be N^N different permutations.


Is Sedgewick wrong or am I missing a fact?


Aucun commentaire:

Enregistrer un commentaire