algorithm - 计算 N 面骰子每个面在 M 次掷骰中出现的次数的最快方法

Question

给定 M 次 N 面骰子，我想生成一个 N 数组，用于存储骰子每个面出现的次数。

例如，对于 6 面骰子，掷 10 次您可能会得到:

[2, 3, 2, 1, 1, 1]

又名 2 1，3 2，2 3，1 4、1 5、1 6.

显而易见的第一个解决方案是生成 M 个随机数并对它们进行计数:

Random r = new Random();
int[] counts = new int[6] { 0, 0, 0, 0, 0, 0 };
for (int i = 0; i < 10; i++) ++counts[(int)Math.Round(r.NextDouble() * 5)];

我想知道是否有更快的东西。我的一个想法是从预期计数开始并应用一些随机“洗牌”:

对于 60 次 6 面骰子，您期望的计数为:

[10, 10, 10, 10, 10, 10]

然后您可以随机选择 2 个索引并加 1 并减 1:

[11, 10, 9, 10, 10, 10]

然后重复此操作 X 次。问题是它实际上并没有给你一个正确的计数，它只是给你一个令人信服的 M 值。另外，你会如何选择 X？

另一个想法是想象一条长度为 M 的线并在其中选择 N 个分割来生成您的组:

9 rolls:

0 1 2 3 4 5 6 7 8 9
|-----------------|
|   | |   | |     |
1   2 3   4 5     6

[2-0, 3-2, 5-3, 6-5, 9-6, 9-9]
[ 2 ,  1 ,  2 ,  1 ,  3 ,  0 ]

此方法的问题是它不能正确表示掷骰子产生的概率。例如配置[3, 0, 0, 1, 1, 1]通过此方法创建的 6 个骰子的出现概率与实际掷骰子的概率不同 3 1，0 2，0 3，1 4、1 5 和 1 6.

也许除了执行掷骰和计数之外，不可能更快地完成此操作。

Answer 1

感谢 Robert Dodier 指出我可以使用多项分布!

在Python中其他人可以查看https://numpy.org/doc/stable/reference/random/generated/numpy.random.multinomial.html

np.random.multinomial(20, [1/6.]*6, size=1)

如果你不能使用 numpy，有很多关于如何实现这一点的文献，但对我来说 numpy 库就足够了，而且运行速度非常快。

对于那些想要了解实现情况的人来说，这里有一些链接:

• https://en.wikipedia.org/wiki/Multinomial_distribution
• https://sites.warnercnr.colostate.edu/gwhite/wp-content/uploads/sites/73/2017/04/MultinomialDistribution.pdf