algorithm - 这个简单的洗牌算法会返回一副随机洗牌的扑克牌吗?

标签 algorithm random shuffle

<分区>

您有一个包含 52 张卡片的列表,其中卡片在该列表中的位置不会移动。 您有第二张卡片位置列表。首先,位置列表与第一个列表相同。

  1. 遍历第一个列表。

  2. 对于第一个列表中的每张卡片,生成一个从 1 到 52 的数字。将其在第二个列表中的位置与该位置的卡片交换。

是否存在偏见?为什么?

更新:从来没有人相信纯数学或逻辑,我决定自己实现。以下是第 5 张牌(按位置)是 1 到 52 中每个数字的概率:

1. 1.9346%
2. 1.9011%
3. 1.8513%
4. 1.8634%
5. 1.8561%
6. 1.8382%
7. 2.5086%
8. 2.4528%
9. 2.4552%
10. 2.3772%
11. 2.3658%
12. 2.3264%
13. 2.3375%
14. 2.287%
15. 2.2627%
16. 2.2151%
17. 2.1846%
18. 2.1776%
19. 2.1441%
20. 2.1103%
21. 2.084%
22. 2.0505%
23. 2.0441%
24. 2.0201%
25. 1.972%
26. 1.9568%
27. 1.9477%
28. 1.9429%
29. 1.9094%
30. 1.8714%
31. 1.8463%
32. 1.8253%
33. 1.8308%
34. 1.8005%
35. 1.7633%
36. 1.7634%
37. 1.769%
38. 1.7269%
39. 1.705%
40. 1.6858%
41. 1.6657%
42. 1.6491%
43. 1.6403%
44. 1.6189%
45. 1.6204%
46. 1.5953%
47. 1.5872%
48. 1.5632%
49. 1.5402%
50. 1.5347%
51. 1.5191%
52. 1.5011%

如您所见,这不是随机的。我希望有一位数学家来证明为什么第 5 张牌比其他任何牌都更可能是 7,但我猜这与早期的牌(如 7)有更多交换机会这一事实有关——这正是正确的算法所阻止的,它只让卡片交换一次。

最佳答案

这是搞砸 Fisher-Yates shuffle algorithm 的常见方式.参见 What distribution do you get from this broken random shuffle?对此实现的属性进行热烈讨论。


这与 Fisher-Yates 有何不同?

对于 Fisher-Yates,在第 k 张牌上,您必须在 k52 之间选择一个随机数。您每次都在 152 之间选择一个随机数。


您描述的方法类似于 What distribution do you get from this broken random shuffle? 中讨论的方法,但可能不完全相同。您的实现类似于井研究“从顶部到随机”洗牌(参见 Diaconis、Fill 和 Pitman 的 Analysis of Top To Random Shuffles),最终将提供完全洗牌的牌组,但不是“一次通过”。 Top to Random shuffle描述如下:

Choose a random number p from 1 to 52, and swap the top card with the card at position p. Continue until the top card is the card originally in position 52, and after this is randomly placed the deck is in random order.

此停止条件称为“停止时间”,需要相当长的时间才能达到。 Fisher-Yates 洗牌要快得多。

关于algorithm - 这个简单的洗牌算法会返回一副随机洗牌的扑克牌吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6637472/

相关文章:

regex - 加快正则表达式匹配?

algorithm - 从给定区域采样

random - FFMpeg random 是否会为连续执行生成相同的伪随机数序列?

r - 如何创建具有高斯分布的随机 (x,y) 点?

python - 在 Python 字典中随机随机排列键和值

perl - 在 Perl 中打乱数组的最佳方法是什么?

java - 3 分区的中位数

python - 双循环的迭代计数器

haskell - 为什么随机类没有最小完整定义

python - 调试 : Shuffle deck of cards in Python/random