2

我目前正在研究一个简单的函数，该函数将对输入的字符串进行打乱，其中所有可能的排列都是同样可能的。我的代码如下。

function scramble(s) {
    result = s.split("");
    for(var i = 0; i < s.length; i++) {
        var j = Math.floor(Math.random() * (i + 1));
        var scrambler = result[i];
        result[i] = result[j];
        result[j] = scrambler;
    }
    return result.join("");
}

到目前为止，代码似乎运行良好......但是所有可能的排列是否同样可能？（我相信 Math.random 和 Math.floor，但是当我在运行时查看 i 和 j 时，我得到了奇怪的输出。）

4

2 回答 2

3

除非我在这里犯了一个可怕的错误（请检查它是否有意义），否则我相信这段代码不会创建均匀分布的排列。

检查例如第一个字符保持原位的机会 - 当 i 为 0 时，它不能被任何人替换，当 i 为 1 时，元素 0 和 1 将有 50% 的机会交换，依此类推。所以总的来说，result[0] 将保持其位置的概率1/2 * 2/3 * 3/4 ... n-1/n = 1/n

但是，最后一个元素留在原地的概率只是 (n-1)/n，因为您只有一次机会交换它，并且您可以从整个数组中进行选择。

如果将 替换为 ，您可能会有更好的分布(i+1)，s.length但最好的选择是采用已知的工作。你可以从这里开始 - http://en.wikipedia.org/wiki/Random_permutation

于 2013-09-23T00:15:08.587 回答
0

深度死灵发布，因为我有一个类似的问题，这是搜索时的第一个结果。我的直觉反应与其他回复相同，但在仔细观察后，OPs 解决方案似乎是 Fisher-Yates 的有效变体。

让我们来看一个使用 OPs 实现的例子。

假设 S = [1,2,3,4]。

第一次迭代：i === 0，j 必须等于 0。不进行任何交换。您可以跳过此循环。

第二次迭代：i === 1，j 可以为 0 或 1。

[1,2,3,4] (j === 1, no swap so same as original),
[2,1,3,4] (j === 0, swap),

请注意，[0-1] 导致 0,1 的所有变化的概率相等

第三次迭代：i === 2，j 可以等于 0,1,2。

[1,2,3,4], [2,1,3,4] (j === 2, no swap so same as previous results),
[1,3,2,4], [2,3,1,4] (j === 1, swaps),
[3,2,1,4], [3,1,2,4] (j === 0, swaps),

请注意，[0-2] 导致 0,1,2 的所有变化的概率相等

第四次迭代：i === 3，j 可以等于 0,1,2,3。

[1,2,3,4], [2,1,3,4], [1,3,2,4], [2,3,1,4], [3,2,1,4], [3,1,2,4] (j === 3, no swap so same as previous results),
[1,2,4,3], [2,1,4,3], [1,3,4,2], [2,3,4,1], [3,2,4,1], [3,1,4,2] (j === 2, swaps),
[1,4,3,2], [2,4,3,1], [1,4,2,3], [2,4,1,3], [3,4,1,2], [3,4,2,1] (j === 1, swaps),
[4,2,3,1], [4,1,3,2], [4,3,2,1], [4,3,1,2], [4,2,1,3], [4,1,2,3] (j === 0, swaps),

再次注意这里的结果是字符串的所有排列等概率！

与Fisher Yates 洗牌的比较

这个工作的原因与链接维基中描述的“现代算法”非常相似

for i from n−1 down to 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

Op 对每个元素执行相同的操作（j 设置在 0 和 i 之间），并以相反的方向循环。每个元素的交换是先完成还是最后完成都不会改变结果。

OPs 实现和 Fisher Yates 都共享@leeor 发布的推理陷阱。即使元素被交换的概率越来越小，但每个元素被交换到每个位置的概率相等，从而为我们提供了所需的结果。

于 2020-10-23T22:26:55.087 回答