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

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

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

不。您的代码和教科书都没有基于乘数值的火箭科学。核心部分是Math.random()函数。您书中的乘数是 i+1，从数学上讲，它获得重复 j 值的概率较低，而您的代码获得重复 j 值的概率稍高，但坦率地说，没关系。

不过，您的代码会稍微快一点，真的快一点，实际上可以忽略不计，因为每次不执行加法运算。

Answer 2

首选第一个示例，因为它确保元素随机排列的公平性。在第二个例子中，元素是随机的，但不是同样随机的。

第一个示例基于未使用 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;
}

来自Collections.shuffle

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

这是一回事。

这可能会快很多，因为它不必产生那么多 "randomness"，这意味着更少的计算。生成双精度数比生成 0 到 9 之间的小数要昂贵得多。

但是，第一个示例没有利用这一点，而是以任何方式调用 Math.random()。仅当您使用 nextInt(n)

时才重要

Answer 3

不，你不能用你的算法代替书上的算法。

解释：你这本书的算法是从一个当前元素开始的，从最后一个元素开始，然后从[0, current]内的所有元素中选择另一个元素，然后交换它们.这样一个更高索引的元素就再也不会被触及了，但它可能最终还是会与自己交换（这是正常的）.

但是，在您的算法中，您正在生成随机索引以从 0 和 i - 1 之间的所有可能索引进行交换。因此，可以在随机播放期间将较高索引的元素交换回其原始位置。

以下代码不等同于您书中的算法。它不会留下任何元素，这在您的书的算法案例中是可能的：

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

是的，它们实际上是不同的。

第一个算法是经典算法的变体Knuth Shuffle。对于这个算法，我们可以证明（例如，通过归纳法），如果我们的随机数生成器 (Math.random()) 是一个理想的生成器，它将生成 n! （n 阶乘）等概率的可能排列。

第二种算法没有这个属性。例如，当 n = 3 时，有 3³ = 27 种可能的结果，并且不能除以 3！ = 6，可能的排列数。实际上，这是结果的概率（生成统计数据的程序：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

对于n=4，结果更加参差不齐，例如（生成统计的程序：3 4）：

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

如您所想，如果您的排列应该是均匀随机的，那么这是不希望的属性。

最后，我们通常使用伪随机数生成器而不是真正的随机源这一事实并不会使上述任何内容无效。我们的随机数生成器的缺陷，如果有的话，显然无法在后面的步骤中修复损坏——如果我们选择非均匀算法，即。

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

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

java

algorithm

shuffle