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.

Answer 2

The first example is preferred as it ensures fairness in how the elements are randomly arranged. In the second example, the elements are random but not equally random.

The first example is based on an optimised version which doesn't use Math.random.

Random rand = ...
for(int i = myList.length-1; i > 0; i--) {
    int j = rand.nextInt(i+1);
    double temp = myList[i];
    myList[i] = myList[j];
    myList[j] = temp;
}

From Collections.shuffle

        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));

which is the same thing.

This can be quite a bit faster as it doesn't have to produce as much "randomness" which means less calculations. Generating a double is far more expensive than a small number say between 0 and 9.

However, the first example doesn't take advantage of this and calls Math.random() any way. It only matters if you use nextInt(n)

Answer 3

No, you cannot use your algorithm in place of the book's algorithm.

---

Explanation: Your book's algorithm starts at a current element, beginning from the last one, and then picks another element from all elements within [0, current] and then swaps them. This way a higher index element can never be touched again, but it may still end up getting swapped with itself (which is normal).

However, in your algorithm you are generating the random index to swap with from all possible indices between 0 and i - 1. Thus, a higher index element can be swapped back to its original location during the shuffle.

---

The following code is not the equivalent of your book's algorithm. It will not leave any element in place, which is possible in your book's algorithm's case:

for (int i = myList.length - 1; i > 0; i--) {
    int j = (int)(Math.random() * i);
    swap(myList, i, j);
}

private void swap(double[] myList, int i, int j) {
    double temp = myList[i];
    myList[i] = myList[j];
    myList[j] = temp;
}

Answer 4

Is there any reason to use the textbook's algorithm over this one?

No. Your code and the text book's both have no rocket science based on the value of the multiplier. The core part is the Math.random() function. The multiplier in your book is i+1 that has mathematically lower probability in getting a repeated j value whereas your code just has a bit higher probability of getting a repeated j value, but frankly speaking, it doesn't matter.

Although, your code would be slightly, really slightly, in fact negligibly faster as each time an addition operation is not performed.