加权随机整数

我想为随机生成的数字指定权重，权重如下所示。

0 | 1 | 2 | 3 | 4 | 5 | 6 ───────────────────────────────────────── X | X | X | X | X | X | X X | X | X | X | X | X | X | X | X | X | X | | X | X | X | X | | | X | X | X | | | | X | X | | | | | X | | | | | | 

什么是最有效的方法？

Answer 1

@Kerrek的回答很好。

但如果权重的直方图不是所有小整数，你需要更强大的东西：

将[0..1]除以用权重确定的间隔。 在这里，您需要相对尺寸比为7：6：5：4：3：2：1的线段。 所以一个间隔单位的大小是1 /（7 + 6 + 5 + 4 + 3 + 2 + 1）= 1/28，间隔的大小是7 / 28,6 / 28，… 1 / 28。

这些包括概率分布，因为它们总和为1。

现在找到累积分布：

 P x 7/28 => 0 13/28 => 1 18/28 => 2 22/28 => 3 25/28 => 4 27/28 => 5 28/28 => 6 

现在在[0..1]中生成一个随机r数，并通过找到最小的x使得r <= P(x)在该表中查找。 这是您想要的随机值。

表查找可以使用二进制搜索来完成，当直方图有许多箱时，这是个好主意。

请注意，您正在有效地构建逆累积密度函数，因此有时将其称为逆变换方法。

Answer 2

如果您的数组很小，只需在以下数组中选择一个统一的随机索引：

 int a[] = {0,0,0,0,0,0,0, 1,1,1,1,1,1, 2,2,2,2,2, 3,3,3,3, 4,4,4, 5,5, 6}; 

如果要在运行时生成分发，请使用std::discrete_distribution 。

Answer 3

为了得到你想要的发行版，首先你基本上把你在那里写的X的数量加起来。 你可以这样做（我的C是超级生锈的，所以把它当作伪代码）

 int num_cols = 7; // for your example int max; if (num_cols % 2 == 0) // even { max = (num_cols+1) * (num_cols/2); } else // odd { max = (num_cols+1) * (num_cols/2) + ((num_cols+1)/2); } 

然后你需要随机选择一个介于1和max之间的整数。

因此，如果您的随机整数是r则最后一步是找到哪个列包含第r个X.这样的东西应该有效：

 for(int i=0;i