时间戳

首页 > 解决方案 > 使用 Math rand 进行改组是如何工作的？

java - 使用 Math rand 进行改组是如何工作的？

问题描述

我看到这段代码来打乱一个列表： 

public static void shuffle(List<Integer> numbers) {
        if(numbers == null || numbers.isEmpty()) return;
        for(int i = 0; i < numbers.size(); ++i) {
            int index = (int) (i + Math.random()*(numbers.size() - i));
            swap(numbers, i, index);
        }
    }

该代码似乎有效，但我不明白这个片段： 

            int index = (int) (i + Math.random()*(numbers.size() - i));

基本上是这样，i + R*(n-i)但这如何确保：i) 我们不会得到越界索引或 ii) 我不会更改相同元素的 ieindex == i并且随机播放不会那么随机？

标签： javaarraylistrandomcollectionsshuffle

解决方案

Math.random()[0, 1)返回区间中的均匀随机数numbers.size() - i，理想情况下，将该数字缩放到区间[0, numbers.size() - i). 例如，如果i是 2 并且列表的大小是 5，[0, 3)则在理想情况下，以这种方式选择区间中的随机数。最后，i被添加到数字并且(int)演员丢弃数字的小数部分。因此，在此示例中，随机生成一个随机整数 in [2, 5)（即 2、3 或 4），因此在每次迭代中，索引 X 处的数字与其自身或它后面的数字交换。

然而，这里有一个重要的微妙之处。由于浮点数的性质和缩放数字时的舍入误差，在极少数情况下，即使输出不包括 1 的数字，输出也Math.random()*(numbers.size() - i)可能等于numbers.size() - iMath.random()。舍入误差会导致习语Math.random()*(numbers.size() - i)使某些结果偏向于其他结果. 例如，只要 2^53 不能被 整除，就会发生这种情况numbers.size() - i，因为在后台Math.random()使用java.util.Random，并且它的算法生成具有 53 位精度的数字。因此，这Math.random()不是编写此代码的最佳方式，并且代码可以使用专门用于生成随机整数的方法（例如 的nextInt方法java.util.Random）。另请参阅此问题还有这个问题。

编辑：事实证明，该Math.random() * integer成语不会产生它可能返回的问题，integer至少在integer任何时候是肯定int的并且像在Java中那样使用四舍五入到最近的舍入模式。看到这个问题。

推荐阅读