以下用于改组数组的算法之间有什么区别吗？

Question

我的 Java 教科书说你可以使用下面的代码随机打乱任何给定的数组：

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;

}

我编写的以下代码是否同样有效或有效？

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;

}

我测试了我的代码，它确实正确地调整了元素。有没有理由在这个算法上使用教科书的算法？

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.