朴素洗牌的现实问题

Question

我正在写一些文章，旨在通过使用与扑克相关的主题来教授入门编程概念。目前，我正在研究洗牌的主题。

作为 杰夫·阿特伍德 (Jeff Atwood) 在 CodingHorror.com 上指出, ，一种简单的洗牌方法（迭代数组并将每张卡与数组中其他位置的随机卡交换）会产生不均匀的排列分布。在实际应用中，我只会使用 Knuth Fisher-Yates 洗牌 以获得更均匀的随机性。但是，我不想用对编码器不太友好的算法来解释编程概念。

这就引出了一个问题：如果黑帽知道你正在使用 52 张牌的简单洗牌方式，他们会有多大优势？看起来它会无限小。

Answer 1

这并不像您正在编写将用于实际在线赌博网站的扑克程序。当你教人们如何编程时，某人在程序中作弊的能力并不是什么大问题。

留下一张纸条，说明这是一个糟糕的现实世界模型（将其称为可能的安全缺陷），然后继续教学。

Answer 2

与 naive shuffle 相比，knuth shuffle 是一个微不足道的变化：只需与牌组剩余（未洗牌）部分中的任何卡牌交换，而不是与整个牌组中的任何位置交换。如果您将其视为从剩余的未选择的卡片中按顺序重复选择下一张卡片，那么它也非常直观。

就我个人而言，我认为，当正确的算法不再复杂（并且更容易可视化！）时，教给学生一个糟糕的算法是一种糟糕的方法。

Answer 3

事实证明，优势还是相当显着的。 看看这篇文章

问题的一部分是算法有缺陷，但另一部分是假设你可以从计算机获得“随机”数字。

Answer 4

一种简单且公平的洗牌算法是为牌组中的每张牌分配一个随机浮点数（例如，0 到 1 之间），然后按分配的数字对牌组进行排序。

这实际上是一个完美的例子，让学生意识到，仅仅因为某些东西是直观的，在我们的例子中，天真的洗牌并不意味着它是正确的。

Answer 5

主观。

看起来它会无限小。

同意。

Answer 6

顺便说一句，有一个 ITtoolbox 上的博客文章 关于模拟洗牌时可能会感兴趣的洗牌。

至于你的问题，考虑一下有52个！人们可以开始使用的牌组配置可能会在事物落地的位置上发挥作用，就像 Jeff 的 3 张牌牌组示例一样，请注意，过度代表中的 1 在每个插槽中出现一次。另请注意，他说你必须有几千个例子才能明显看出优势在哪里，但是对于一副牌，你不太可能用完全相同的初始牌重新开始，是吗？你会把发到的牌放在底部，然后洗牌，我认为这不太可能重复。