朴素洗牌的现实问题
我正在写一些文章，旨在通过使用与扑克相关的主题来教授入门编程概念。 目前，我正在研究洗牌的主题。
正如 Jeff Atwood 在 CodingHorror.com 上指出的，一种简单的洗牌方法（迭代数组并将每张卡与数组中其他位置的随机卡交换）会产生不均匀的排列分布。 在实际的应用程序中，我只使用 Knuth Fisher-Yates shuffle 以获得更均匀的随机性。 但是，我不想用对编码器不太友好的算法来解释编程概念。
这就引出了一个问题：如果黑帽知道你正在使用 52 张牌的简单洗牌方式，他们会有多大的优势？ 看起来它会无限小。
I'm writing a number of articles meant to teach beginning programming concepts through the use of poker-related topics. Currently, I'm working on the subject of shuffling.
As Jeff Atwood points out on CodingHorror.com, one simple shuffling method (iterating through an array and swapping each card with a random card elsewhere in the array) creates an uneven distribution of permutations. In an actual application, I would just use the Knuth Fisher-Yates shuffle for more uniform randomness. But, I don't want to bog down an explanation of programming concepts with the much less coder-friendly algorithm.
This leads to the question: Just how much of an advantage would a black-hat have if they knew you were using a naive shuffle of a 52-card deck? It seems like it would be infinitesimally small.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
顺便说一句，ITtoolbox 上有一篇博客文章< /a> 关于模拟洗牌时可能会感兴趣的洗牌。
至于你的问题，考虑一下有52个！ 人们可以开始使用的牌组配置可能会在事物落地的位置上发挥作用，就像 Jeff 的 3 张牌牌组示例一样，请注意，过度代表中的 1 在每个插槽中出现一次。 另请注意，他说你必须有几千个例子才能明显看出优势在哪里，但是对于一副牌，你不太可能用完全相同的初始牌重新开始，是吗？ 你会把发到的牌放在底部，然后洗牌，我认为这不太可能重复。
Just as an aside, there was a blog post over on ITtoolbox about shuffling that may be of interest when it comes to simulating a shuffle.
As to your question, consider that there are 52! deck configurations that one could start with that may play a role in where things land as in Jeff's example of the 3 card deck, note that the 1 in the over-represented occurs in each slot once. Also note that he says you'd have to have a few thousand examples before it becomes apparent where the advantage is, but with a deck you aren't likely to start again with the exact same initial deck, are you? You'd take the dealt cards and put them on the bottom and shuffle them which isn't likely to repeat I'd think.
一个简单的& 公平的洗牌算法是为这副牌中的每张牌分配一个随机浮点数（例如，0 到 1 之间），然后按分配的数字对这副牌进行排序。
这实际上是一个完美的例子，让学生认识到，仅仅因为某些东西是直观的，在我们的例子中，天真的洗牌并不意味着它是正确的。
A simple & fair algorithm for shuffling would be to assign a random floating-point number (e.g., between 0 and 1) to each card in the deck, then sort the deck by the assigned numbers.
This is actually a perfect example for students to realize that just because something is intuitive, the naive shuffle in our case, doesn't mean it's correct.
事实证明，优势还是相当显着的。 查看这篇文章
部分问题是算法有缺陷，但另一部分是是假设您可以从计算机获得“随机”数字。
It turns out the advantage is quite significant. Check out this article
Part of the problem is the flawed algorithm, but another part is the assumption that you can get "random" numbers from a computer.
与简单的洗牌相比，克努斯洗牌是一个微不足道的变化：只需与牌组剩余（未洗牌）部分中的任何卡交换，而不是与整个牌组中的任何位置交换。 如果您将其视为从剩余的未选择的卡片中按顺序重复选择下一张卡片，那么它也非常直观。
就我个人而言，我认为，当正确的算法不再复杂（并且更容易可视化！）时，教给学生一个糟糕的算法是一种糟糕的方法。
The knuth shuffle is an insignificant change compared to the naive shuffle: Just swap with any card in the remaining (unshuffled) section of the deck instead of anywhere in the entire deck. If you think of it as repeatedly choosing the next card in order from the remaining unchosen cards, it's pretty intuitive, too.
Personally, I think teaching students a poor algorithm when the proper one is no more complicated (and easier to visualise!) is a bad approach.
主观。
同意。
Subjective.
Agree.
这并不像您正在编写将用于实际在线赌博网站的扑克程序。 当你教人们如何编程时，某人在程序中作弊的能力并不是什么大问题。
留下一张纸条，说明这是一个糟糕的现实世界模型（将其称为可能的安全缺陷），然后继续教学。
It's not like you're writing a poker program that will be used for an actual online gambling site. An ability for someone to cheat at the program isn't a big deal when you're teaching people how to program.
Leave a note saying that this is a poor model of the real world (with a reference to it as a possible security flaw), and just keep going with the teaching.