Is there any difference between the following algorithms for shuffling arrays?

Question

My Java textbook says that you can use the following code to randomly shuffle any given array:

for(int i = myList.length-1; i >=0; i--)
{

    int j = (int)( Math.random() * (i+1) );
    double temp = myList[i];
    myList[i] = myList[j];
    myList[j] = temp;

}

Would the following code that I wrote would be equally efficient or valid?

for(int i = 0; i < myList.length; i++)
{

    int j = (int)( Math.random() * (myList.length) );
    double temp = myList[i];
    myList[i] = myList[j];
    myList[j] = temp;

}

I tested my code and it does shuffle the elements properly. Is there any reason to use the textbook's algorithm over this one?

Answer 1

Yes, they are in fact different.

The first algorithm is a variant of the classic Knuth Shuffle. For this algorithm, we can prove (e.g., by induction) that, if our random number generator (Math.random()) was an ideal one, it would generate every one of the n! (n factorial) possible permutations with equal probability.

---

The second algorithm does not have this property. For example, when n = 3, there are 3³ = 27 possible outcomes, and that does not divide evenly by 3! = 6, the number of possible permutations. Indeed, here are the probabilities of outcomes (programs generating statistics: 1 2):

[0, 1, 2] 4/27
[0, 2, 1] 5/27
[1, 0, 2] 5/27
[1, 2, 0] 5/27
[2, 0, 1] 4/27
[2, 1, 0] 4/27

For n = 4, the results are even more uneven, for example (programs generating statistics: 3 4):

[1, 0, 3, 2] has probability 15/256
[3, 0, 1, 2] has probability  8/256

As you can imagine, this is an undesired property if your permutation is supposed to be uniformly random.

---

Lastly, the fact that we usually use a pseudorandom number generator instead of a true random source does not invalidate any of the above. The defects of our random number generator, if any, are obviously unable to repair the damage at the later step - if we choose a non-uniform algorithm, that is.