洗牌一副牌

Question

我正在为一个C++程序制作一种牌组类。它需要有两个方法：一个用于从顶部弹出一张卡牌，另一个用于洗牌。我关注后者。

卡牌被表示为整数1到52（包括52）。假设水平良好，最快的洗牌算法是什么？

- oadams

Answer 1

如果您希望自己实现洗牌算法，可以使用一个非常简单但也很实用的洗牌算法：Fisher–Yates shuffle。

要对包含n个元素的数组a进行洗牌：

for i from n − 1 downto 1 do
   j ← random integer with 0 ≤ j ≤ i
   exchange a[j] and a[i]

当然，C++标准库也已经为你实现了这样的功能，例如通过<algorithm>头文件包含的std::random_shuffle。

- Amber

---

洗牌一旦掌握方法就很容易。如果你没有在数学课上学习随机性，很容易出错。 - Martin York

@Martin：如果你不能遵循简单的指示，那么很容易出错；-p - Steve Jessop

@Steve：即使我知道Amber想说什么，但我也很难读懂上面的内容。唯一简单的方法就是使用预先构建的算法。我敢打赌，如果我们让10个分数低于1000的人用C++实现它，其中有2个会做错。请将所有提交发送给Steve。 :-0 - Martin York

从 n-1 循环到 1：有没有可能 a[0] 的概率很高是相同的值？为什么不用 downto 0？ - Han

@Han 如果 j = 0，则可以在循环的任何迭代中交换 a[0]。如果 i 等于零，则 j 也必须等于零（因为循环体的第一行将 j 设置为小于或等于零的随机整数），这不会改变排序。 - Amber

Answer 2

使用std::random_shuffle来洗牌。

- James McNellis

Answer 3

std::random_shuffle

http://www.cplusplus.com/reference/algorithm/random_shuffle/

- Benjamin Lindley