这种与数学兰特的洗牌是如何工作的?

Question

我看到这段代码来洗牌列表：

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)我不会更改相同的元素，即index == i洗牌不会那么随机吗？

Answer 1

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

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

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

Answer 2

Math.random() 总是返回一个介于 0(含)和 1(不包括)之间的浮点数。因此，当您执行Math.random()*(numbers.size() - i)时，结果将始终介于 0(含)和n-i(不包括)之间。

然后你在i + Math.random()*(numbers.size() - i)中添加 i 到它。

现在，如您所见，结果将介于 i(含)和 n(不含)之间。

之后，您将将其转换为整数。当你将双精度转换为 int 时，你会截断它，所以现在索引的值将从 ''iton - 1'''(包括两者)。

因此，您将不会有 ArrayIndexOutOfBoundsException，因为它总是至少比数组的大小小 1。

但是，索引的值可以等于 i，所以是的，你是对的，因为一个数字可以与自身交换并保持在那里。这完全没问题。

Answer 3

1. 您有一个包含 1 到 50 个整数的列表。

2. 因此，获取一个从 0 到 49 的随机值(包括 0 到 49)来索引它。 假设是30。

3. 获取索引 30 处的项目。

4. 现在将索引 30 中的项目替换为索引 49 中的项目。

5. 下次生成一个介于 0 和 48 之间的数字(包括 0 和 48)。 永远不会达到 49，那里的数字占用最后一个使用的号码的插槽。

6. 继续此过程，直到用尽列表。

注意：表达式(int)(Math.random() * n)将生成一个介于0和n-1之间的随机数，因为Math.random生成一个介于0和1排除之间的数字。

Answer 4

与其使用这样的自定义方法，我建议您使用 OOTB Collections.shuffle。检查此项以了解为Collections.shuffle实现的逻辑。

代码分析：

Math.random() 返回一个带有正号、大于或等于0.0且小于1.0的double值。

现在，让我们假设numbers.size() = 5并试运行for循环：

When i = 0, index = (int) (0 + Math.random()*(5 - 0)) = (int) (0 + 4.x) = 4
When i = 1, index = (int) (1 + Math.random()*(5 - 1)) = (int) (1 + 3.x) = 4
When i = 2, index = (int) (2 + Math.random()*(5 - 2)) = (int) (2 + 2.x) = 4
When i = 3, index = (int) (3 + Math.random()*(5 - 3)) = (int) (3 + 1.x) = 4
When i = 4, index = (int) (4 + Math.random()*(5 - 4)) = (int) (4 + 0.x) = 4

如您所见，当numbers.size() = 5时，index的值将在每次迭代中保持4。

您的查询：

这如何确保：i)我们不会获得越界索引

正如上面已经解释的那样，使用试运行，它永远不会越界。

或 ii) 我不会更改相同的元素，即索引 == i 和 洗牌不会那么随机吗？

swap(numbers, i, index);在索引处交换元素，i与索引处的元素交换，4每次numbers.size() = 5时。以下示例对此进行了说明：

假设numbers= [1， 2， 3， 4， 5]

When i = 0, numbers will become [5, 2, 3, 4, 1]
When i = 1, numbers will become [5, 1, 3, 4, 2]
When i = 2, numbers will become [5, 1, 2, 4, 3]
When i = 3, numbers will become [5, 1, 2, 3, 4]
When i = 4, numbers will become [5, 1, 2, 3, 4]

Answer 5

1. int index = (int) (i + Math.random()*(numbers.size() - i));- 重要的是要注意 Math.random() 将生成一个属于 <0 的数字;所以它永远不会超过边界，因为排除最大值将是：i + 1*(number.size() -i) = number.size
2. 这一点是有效的，它可能发生。