0

我想知道你们中的一些人是否了解 Fisher-Yates shuffle 的工作原理并可以向我解释。所以我在网上找到了这个 Fisher-Yates Shuffle 代码：

public function Main() {
var tempArray:Array = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
ShuffleArray(tempArray);
trace(tempArray);
}
public function ShuffleArray(input:Array)
{
for (var i:int = input.length-1; i >=0; i--)
{
var randomIndex:int = Math.floor(Math.random()*(i+1));
var itemAtIndex:Object = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
}

该代码完美运行，但我仍然感到困惑

  1. 我将循环更改为“input.length”，但效果不佳，有时我仍然得到“0”值。我不知道为什么要使用“input.length-1”而不是“input.length”
  2. 在 randomize 部分，为什么我要将索引从 0 随机化到值 (i+1)，我们为什么不直接将它从 0 随机化到 (i) 呢？

如果你们中的一些人理解它，你能解释一下吗？太感谢了

4

2 回答 2

0

  1. Js 的数组索引从 0 开始，所以a长度n为 的数组的最后一个元素是a[n -1]。

  2. Math.random 返回一个从 0 到 0.9999.... 的值，但不包括 1(range at [0, 1))，所以Math.random()* (i + 1), 会有一个0to的值i + 0.999999......，而不是i + 1(range [0, i+1))，并用于Math.floor切割点部分以获得 a Integer，所以我们得到一个范围内的数字[0, i]。

于 2015-06-27T14:48:13.933 回答
0

让我用一个否定的例子来解释让我们说数组大小是 10。

1）如果我们在 for 循环中使用 index.length 第 3 行将读取

input[randomIndex] = input[i] i.e.
input[randomIndex] = input[10];

但由于 javascript 有基于 0 的数组，它的值从索引 0 到 9 。索引 10 将超出范围。因此我们应该从最后一个元素开始洗牌（仅限索引 9）

2）对于您的第二个问题，如果我们使用 i 而不是 i+1。假设您处于索引 9 的循环的第一次迭代中（对于其他迭代也适用）。这里 i 是 9，如上所示。我们希望将第 9 个索引从 0 到 9 的任何一个索引中洗牌 Math.random 将从 0 返回到 .999 并且 Math.floor 将对其下限，因此在我们的例子中，最大值将是 .999 * (9+1) = 9.99 .Math.floor 将其下限为 9.所以范围是 [0,9]

如果我们使用 i 的最大可能值为 8，即 Range[0,8]

因此我们使用 i+1 因为我们想要来自 [0,9] 的值

于 2015-06-27T15:01:48.827 回答