为什么这个洗牌算法没有偏见

Question

我和我的同事正在争论为什么 JS 提示列表中给出的随机播放算法;技巧不会产生像 Jeff Atwood 描述用于简单的洗牌。

提示中的数组洗牌代码是：

list.sort(function() Math.random() - 0.5);

Jeff 的天真的洗牌代码是：

for (int i = 0; i < cards.Length; i++)
{
  int n = rand.Next(cards.Length);
  Swap(ref cards[i], ref cards[n]);
}

我编写了这个 JS 来测试洗牌：

var list = [1,2,3];
var result = {123:0,132:0,321:0,213:0,231:0,312:0};
function shuffle() { return Math.random() - 0.5; }
for (var i=0; i<60000000; i++) {
    result[ list.sort(shuffle).join('') ]++;
}

为此，我得到的结果（来自 Firefox 5）如下：

Order   Count          %Diff True Avg
123      9997461       -0.0002539
132     10003451        0.0003451
213     10001507        0.0001507
231      9997563       -0.0002437
312      9995658       -0.0004342
321     10004360        0.000436

大概 Array.sort 正在走list 数组并执行（相邻）元素的交换，类似于 Jeff 的示例。那么为什么结果看起来没有偏见呢？

Answer 1

我发现它显得公正的原因。

Array.sort() 不仅返回数组，它还改变数组本身。如果我们为每个循环重新初始化数组，我们会得到如下结果：

123 14941
132 7530
321 7377
213 15189
231 7455
312 7508

这显示了非常显着的偏差。

对于那些感兴趣的人，这里是修改后的代码：

var result = {123:0,132:0,321:0,213:0,231:0,312:0};
var iterations = 60000;
function shuffle() { 
    comparisons++;
    return Math.random() - 0.5;
}
for (var i=0; i<iterations; i++) {
    var list = [1,2,3];
    result[ list.sort(shuffle).join('') ]++;
}
console.log(result);

Answer 2

天真的洗牌的问题是该值可能已经被交换，您可能稍后会再次交换它。假设您有三张牌，并且您真正随机选择一张作为第一张牌。如果您稍后可以随机将该卡与后一张卡交换，那么您就失去了第一个选择的随机性。

如果排序是快速排序，它会不断地将列表分成两半。下一次迭代将每个组随机分为两组。这样一直持续下去，直到只剩下一张牌，然后将它们组合在一起。不同之处在于，您永远不会从第二个随机选择的组中取出一张卡并将其移回第一组。

Knuth-Fisher-Yates 洗牌与朴素洗牌不同，因为您只选择一张牌一次。如果你从一副牌中随机挑选一张牌，你会放回一张牌并再次挑选吗？不，你一次随机拿一张牌。这是我第一次听说它，但我在高中时就从索引 0 开始做过类似的事情。 KFY 可能更快，因为我在随机语句中添加了额外的内容。

for (int i = 0; i < cards.Length - 1; i++)
{
  int n = rand.Next(cards.Length - i) + i; // (i to cards.Length - 1)
  Swap(ref cards[i], ref cards[n]);
}

不要将其视为交换，而应将其视为从牌组中随机选择牌。对于数组中的每个元素（除了最后一个元素，因为只剩下一张），您从所有剩余卡片中随机选择一张卡片，并将其放下，形成一堆随机洗牌的新卡片。如果您已经进行了任何交换，那么您剩余的牌不再按原始顺序并不重要，您仍然可以从所有剩余的牌中随机挑选一张牌。

随机快速排序就像拿一堆纸牌并将它们随机分成两组，然后将每组纸牌随机分成两个较小的组，如此反复，直到获得单独的纸牌，然后将它们放回一起。

Answer 3

实际上，这并没有实现他天真的随机排序。他的算法实际上手动转置数组键，而排序则主动对列表进行排序。

排序使用 quicksort 或 插入排序（感谢cwolves指出这一点——见评论）来做到这一点（这将根据实现而变化）：

1. A比B大还是小？更小？递减。
2. A 比 C 大还是小？更小？递减。
3. A 比 D 大还是小？更小？在 D 之后插入 A
4. B 比 C 大还是小？更小？递减。
5. B 比 D 大还是小？更小？在 D 之后和 A 之前插入 B...

这意味着每次循环迭代，平均情况下的大 O 是 O(n log n)，最坏情况下的大 O 是 O(n^2)。

同时，阿特伍德朴素随机排序很简单：

1. 从 A 开始。查找随机值。交换。
2. 转到 B。查找随机值。交换。
3. 转到 C. 查找随机值。交换。

（Knuth-Fisher-Yates 几乎是一样的，只是向后）

所以他的 O(n) 最坏情况有一个大，O(n) 的平均情况有一个大 O。