为什么这个简单的洗牌算法（通过 random() 排序）存在偏差？

In 这个线程 https://stackoverflow.com/a/18650169/17102262我们看到这个简单而漂亮的算法来洗牌数组：

function shuffle<T>(array: T[]): T[] {
  return array.sort(() => Math.random() - 0.5);
}

我们可以看到评论说这个算法有偏见。但我制作了一个简单的脚本来创建数组最后一个元素在洗牌后结束的索引的经验概率分布：

function shuffle(array) {
  return array.sort(() => Math.random() - 0.5);
}

function generateDistribution(iterations = 10_000, arrayLength = 10) {
  const testArray = Array(arrayLength - 1).fill("test");
  const testTarget = "target";
  testArray.push(testTarget);

  const results = {};

  for (let index = 0; index < iterations; index++) {
    countTargetPosition();
  }

  return generateResult();

  function countTargetPosition() {
    const shuffled = shuffle(testArray);
    shuffled.forEach((value, index) => {
      if (value === testTarget) {
        results[index] = results[index] + 1 || 1;
      }
    });
  }

  function generateResult() {
    return Object.entries(results).map(([index, count]) => {
      return {
        [index]: count / iterations,
      };
    });
  }
}

const result = generateDistribution()
document.write(`<h1>Result</h1>`)

document.write(JSON.stringify(result))

我们期望无偏算法具有均匀分布，并且结果非常接近该分布，即使对于具有 100 个元素的数组也是如此。那么为什么这个算法会有偏差呢？

JavaScript 没有指定特定的算法sort，并且根据所使用的特定排序算法，这种洗牌算法可能会给出非常有偏差的结果。下面，我描述了一些简单的、众所周知的排序算法，这些算法给出了非常有偏差的结果；我证明 Firefox 和 Chrome 对于长度为 4 的数组都给出了非常有偏差的结果；我给出了一个一般性的理由来解释为什么any排序算法会给出有偏差的结果（尽管不一定as这些明确的例子有偏见）。

示例#1 —选择排序 https://en.wikipedia.org/wiki/Selection_sort.在选择排序中，我们首先找到最小的元素并将其放在索引 0 处，然后找到第二小的元素并将其放在索引 1 处，依此类推。需要注意的是，使用比较函数() => Math.random() - 0.5，比较的每个参数都有相同的机会被视为“较少”。因此，如果您通过迭代数组并将每个元素与之前的最小元素进行比较来找到最小元素，那么您有 50% 的机会认为最后一个元素是最小的，有 25% 的机会认为最后一个元素是最小的。认为倒数第二个元素是最少的，您有 12.5% 的机会认为倒数第三个元素是最少的，等等，因此给出了哪个元素先出现的有偏分布。

示例 2 —插入排序 https://en.wikipedia.org/wiki/Insertion_sort.在插入排序中，我们通过依次取出每个元素并将其插入到该排序部分中的正确位置（将所有较大的元素移动一位以为其腾出空间）来构建数组的“已排序”部分。这意味着最后一个元素有 50% 的机会被视为最少，25% 的机会被视为第二少，12.5% 的机会被视为第三少，等等。

示例 #3 和 #4 — Firefox 和 Chrome 使用的四元素数组。

现在，实际上，我不期望任何实施sort to use exactly选择排序或插入排序，因为还有其他算法对于大输入更有效。但复杂的现代排序算法，例如Timsort https://en.wikipedia.org/wiki/Timsort，结合多种不同的排序算法，根据输入（或部分输入，因为它们可以以复杂的方式组合这些算法）的大小和特征在它们之间进行自适应选择。因此，作为实验，我在数组上尝试了这种洗牌算法[1, 2, 3, 4]- 一个足够短的数组，看起来很可能sort实现可能只对整个数组使用插入排序。

这是我使用的代码：

const counts = {};
for (let i = 0; i < 1_000_000; ++i) {
  const permutation = [1, 2, 3, 4].sort(() => Math.random() - 0.5).join('');
  counts[permutation] = (counts[permutation]||0) + 1;
}

const result = [];
for (let permutation in counts) {
  result.push(permutation + ': ' + counts[permutation]);
}

result.join('\n')

我在 Firefox 和 Chrome 中都尝试过这个。

在 Firefox 中，我得到了这样的结果：

1234: 125747
1243: 62365
1324: 62299
1342: 31003
1423: 31320
1432: 15635
2134: 125380
2143: 62216
2314: 62615
2341: 31255
2413: 31509
2431: 15608
3124: 62377
3142: 31166
3214: 62194
3241: 31293
3412: 15631
3421: 15782
4123: 31056
4132: 15672
4213: 31231
4231: 15319
4312: 15727
4321: 15600

这与我对插入排序的期望不符，所以它必须做一些不同的事情，但无论如何，它显示出非常明显的偏差。有些排列发生的时间为 1/64（一百万次中有 15,625 次，加上/减去随机噪声），有些排列发生的时间为 1/32 (31,250)，有些排列的发生时间为 1/16 (62,500)，有些排列发生的时间为 1/16 (62,500)。发生次数为 1/8 (125,000)；因此，某些排列的出现频率是其他排列的八倍。

在 Chrome 中，我得到了这样的结果：

1234: 187029
1243: 62380
1324: 15409
1342: 15679
1423: 62476
1432: 15368
2134: 31280
2143: 31291
2314: 15683
2341: 15482
2413: 31482
2431: 15732
3124: 15786
3142: 15692
3214: 47186
3241: 47092
3412: 15509
3421: 46600
4123: 62825
4132: 15595
4213: 31091
4231: 15763
4312: 15624
4321: 171946

which also与我对插入排序的期望不符，并且比 Firefox 中的分布要复杂一些（我想我在那里看到了一些 3/16（187,500）和 3/64（46,875）？），但是实际上，偏差甚至更大，最常见的排列和最不常见的排列之间存在十二倍的差异。

Example #5 — any deterministic sorting algorithm. I've given various examples above of fairly extreme biases; but really, any sorting algorithm would be expected to produce some bias, because if the algorithm does worst-case k comparisons on an array of length n, and each comparison has a 50–50 split, then the probability of any given permutation has to be a multiple of ¹/_2^k, whereas an unbiased shuffler has to give each permutation the probability ¹/_n!, which won't be a multiple of ¹/_2^k if n ≥ 3 (because then n! will be a multiple of 3).

也就是说，我应该承认这些偏见可能足够小，以至于无关紧要。毕竟，即使1.0 / 3.0不计算exactly1/3，而是将其四舍五入为二进制近似值。更直接的相关性是，一个典型的实现Math.random()保存 64 或 128 位内部状态，这意味着它甚至没有 21 位！或 35！不同的内部状态，这意味着no使用的算法Math.random()打乱 21 个或 35 个或更多元素的数组可以possibly以非零概率产生每个排列。所以我想some偏见是不可避免的！

即使您使用的是sort给出您考虑的结果的实施够好了，没有理由这样做，因为费舍尔-耶茨洗牌 https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle编码简单and比任何基于比较的排序算法都要快。

但我制作了一个简单的脚本来创建数组最后一个元素在洗牌后结束的索引的经验概率分布：[...]

请注意，可能存在更微妙的偏差，因此并非所有排列的可能性都相同even if最后一个元素同样有可能出现在任何位置。即使sort实现保持固定，您需要在依赖此改组算法给出无偏差结果之前进行更彻底的分析（可能包括查看其源代码）。