洗牌算法分析 [英] Shuffling algorithm analysis

问题描述

我碰到的洗牌算法此以下分析：

I came across this following analysis of shuffling algorithms:

问：考虑到不同的整数数组，给出一个算法随机   重新排列的整数，使得每个可能的重排序也同样   可能的。换句话说，给定一个副牌，你怎么洗牌   他们使得卡的任意排列是同样可能？

Q: Given an array of distinct integers, give an algorithm to randomly reorder the integers so that each possible reordering is equally likely. In other words, given a deck of cards, how can you shuffle them such that any permutation of cards is equally likely?

很好的回答：穿过为了元素，交换了每个元素   随机元件的阵列中不早于出现   元件。这需要O（n）的时间。注意，有几种可能的   解决这个问题，以及一些好看的答案   那是不正确的。例如，稍微修改上述   算法，由此一个交换机的每个元素的任何元素   阵列的不给每个重排有同样的概率

Good answer: Go through the elements in order, swapping each element with a random element in the array that does not appear earlier than the element. This takes O(n) time. Note that there are several possible solutions to this problem, as well as several good‐looking answers that are incorrect. For example, a slight modification to the above algorithm whereby one switches each element with any element in the array does not give each reordering with equally probability.

我想知道的是，为什么开关每个元素的数组中的任何其他元素不产生了良好的洗牌，而不是使用克努特洗牌（这说明）。此外，如何在高德纳洗牌选择值以相同的概率？任何数学或证明是极大的AP preciated。

What I would like to know is why switching each element with any other element in the array does not produce a good shuffle as opposed to using the Knuth shuffle (which is described). Also, how does the Knuth shuffle select values with equal probability? Any math or proof is greatly appreciated.

推荐答案

最简单的证明，这种算法不产生均匀随机排列

The easiest proof that this algorithm does not produce a uniformly random permutation

for (int i = 0; i < 3; ++i) {
   swap(a[i], a[rand() % 3]);
}

时，它会产生27个可能的结果，但只有3个！ = 6排列。因为6不分27，必须有一些置换]是拾取太多，以及一些被拾取到小

Is that it generates 27 possible outcomes, but there are only 3! = 6 permutations. Since 6 does not divide 27, there must be some permutation is that is picked too much, and some that is picked to little.

为什么是一个O（n）的算法优化？那么，随机洗牌有时必须触摸每个输入（改变它们），所以任何优化算法需要做至少为O（n）的工作。

Why is an O(n) algorithm optimal? Well, a random shuffle must touch every input sometimes (to change them), so any optimal algorithm needs to do at least O(n) work.

为什么克努特算法是否正确？这需要一点点更深入的了解。可以通过诱导证明所述第一项被选中与正确的概率（每个项目是同样可能是第一），然后再证明该感应步骤持有作为你前进通过循环，使第二，第三等物品还选择与从阵列的剩余部分的正确概率

Why is the Knuth algorithm correct? That requires a little bit more insight. You can prove via induction that the first item is selected with the correct probability (each item is equally likely to be first), and then prove that the inductive step holds as you advance through the loop, that the second, third, etc items are also selected with the correct probability from the remaining portions of the array.

这篇关于洗牌算法分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！