如何从一个反比加权列表中进行随机选择？

Question

给定一个整数列表，例如1, 2, 3, 4，我知道如何根据它们的权重选择项目。这些示例项目的概率分别为10％，20％，30％和40％。

是否有一种同样简单的方法可以根据它们的权重倒数选择项目？使用此方法，示例列表将等于加权列表1，1/2，1/3，1/4（48％，24％，16％，12％），但我想避免浮点算术的转换和使用。（假设所有整数均为正且非零。）

- dlras2

Answer 1

你可以将数字的最小公倍数除以每个数字，得到整数比例。

对于[1, 2, 3, 4]来说，这是12。你的权重分别为12/1=12、12/2=6、12/3=4、12/4=3。

你也可以将它们全部相乘，不需要关心最小公倍数。数字会更大，但比例是相同的：24/1=24、24/2=12、24/3=8、24/4=6。

- Platinum Azure

---

我刚刚想出了这个解决方案。只需要重新写下来并思考几分钟就可以了。 - dlras2

别担心，我会的。不过我还得再等4分钟。=P - dlras2

这种方法的问题在于，对于大的 n 值，你会遇到整数溢出问题。即使使用 64 位长整型，在 n 约为 25 的情况下也会失败。 - tskuzzy

假设对于较大的数字，我们会使用可以避免这种情况的数据类型。大多数编程语言至少在一个库中支持大数操作。 - Platinum Azure

Answer 2

首先，获取权重的总和，称之为S（例如：1 + 1/2 + 1/3 + 1/4 = 2.083）。然后，要找到权重w_i的概率，您需要将w_i除以S（例如：1/2.083 = 48%）。

我认为对于一般的数字序列，这个表达式没有一个漂亮的、封闭的公式。

权重的总和是调和数。对于大的n，总和收敛于ln(n)+gamma，其中gamma是欧拉-马斯刻罗尼常数（约为0.577）。因此，对于大的n，您可以使用这个公式来近似计算总和。

编辑：有方法可以减少浮点误差。其中一种方法是从最小项到最大项计算总和（例如：1/n + 1/(n-1) + ... + 1）。这样可以使中间计算最大化精度位数。通过这样做，舍入问题不应该成为问题。

- tskuzzy

---

这正是我试图避免的浮点数运算类型。 - dlras2

已根据要求修改了我的答案。 - tskuzzy