参见英文答案 >
What distribution do you get from this broken random shuffle?10个
所以,我正在观看Robert Sedgewick关于Coursera的视频,而我现在正在洗牌.他正在为在线扑克显示一个“写得不好”的洗牌代码(它还有一些其他错误,我已经将其删除,因为它们与我的问题无关)这就是算法的工作原理：
所以,我正在观看Robert Sedgewick关于Coursera的视频,而我现在正在洗牌.他正在为在线扑克显示一个“写得不好”的洗牌代码(它还有一些其他错误,我已经将其删除,因为它们与我的问题无关)这就是算法的工作原理：
for(int i = 0; i < N; i++) int r = new Random().nextInt(53); swap(cardArray,i,r);
它迭代所有卡片一次.在每次迭代中,生成随机数,并且第i个卡与第r个卡交换.简单吧？
虽然我理解算法,但我不理解他的概率计算.他说,因为Random使用32位种子(或64,它似乎并不重要),这仅限于2 ^ 32种不同的排列.
他还说Knuth的算法更好(循环相同,但选择1和i之间的数字),因为它给你N！排列.
我同意Knuth的算法计算.但我认为在第一个(应该是错误的)上应该有N ^ N个不同的排列.
塞奇威克错了还是我错过了一个事实？
解决方法
Sedgewick解释它的方式对我来说似乎很奇怪和迟钝.
想象一下,你只有3张牌,并应用了所示的算法.
交换第一张卡后,将有3种可能的结果.在第二次,第9次交换之后,在第三次交换之后,27.因此,我们知道使用交换算法我们将有27种不同的可能结果,其中一些将是其他结果的重复结果.
现在,我们知道有一个事实,即3张牌组有3 * 2 * 1 = 6种可能的安排.然而,27不能被6整除.因此,我们知道某些安排会比其他安排更常见,即使没有计算它们是什么.因此,交换算法不会在6种可能性中产生相等的概率,即,它将偏向某些安排.
同样的确切逻辑延伸到52张卡的情况.
我们可以通过查看三卡案例中的结果分布来调查哪些安排是首选的,它们是：
1 2 3 5次发生
1 3 2 5次发生
2 1 3 4次发生
2 3 1 4次发生
3 1 2 4次发生
3 2 1 5次发生
总计27
检查这些,我们注意到需要0或1次交换的组合比需要2次交换的组合具有更多的出现次数.通常,组合所需的交换次数越少,就越有可能.
