请教一个抽奖的算法

[xing393939]

假设抽奖有两个奖品 A 和 B ，中奖概率都是 50%，我的实现是用随机数来确定每次抽奖中哪个，但是问题是会有误差，比如某次的抽奖统计结果是：A 被抽中 500 次，B 被抽中 471 次。产品经理认为误差有点大，他想要比较精准的概率。

我现在想实现一个绝对公平的抽奖算法，例如，第一次抽奖可以是随机的，比如中了 B ，那么第二次一定中 A ，第三次一定中 B ，循环往复。

而这种在只有两个奖品的时候，还是好实现的，问题是奖品可能是三个，四个......，中奖概率也是可以任意分配的，这样的有什么好的算法去实现吗？

我按照自己的想法实现了一个，大家觉得可以吗：

https://gist.github.com/xing393939/8c487e53b573b9f2795d6eac54e9830b

[brader]

数学概率就是这样的啊，只有次数足够大的时候，概率才会比较接近。
如果非要人为干预的话，你可以设计一个加权概率来纠偏，比如你的理想概率是 a%、b%、c%，然后你还有一个当前的实际概率 a1%、b1%、c1%，那你计算到，比如 a1%比 Z%a 小了超过一定阈值，你就给 a 这个概率加权，要细分，就分多个档次，偏的越多，加权越多

[brader]

@brader 手误，Z%a 纠正为 a%

[ricwangcom]

这还需要算法？按请求顺序下发奖品不就行了[狗头]，ABABABABABABABABABABABAB

[xing393939]

@brader 谢谢，我也是这样想的，我是想问问有没有专门解决这类问题的经典算法。

[R18]

奖品总数是固定的吗？如果是这样，就生成好队列。每次都取一个出来，取到哪个是哪个。

[murmur]

如果是公司内部抽奖，领导主动放弃参与，员工随机抽，这就是最公平的
如果是活动对外抽奖，外人一定不会中特等奖，只能中参与奖

哪里有绝对公平

[murmur]

你的需求来看不像抽奖，倒像是原神的保底，如果第一次歪了第二个金一定是当期 up

[bsg1992]

游戏的暴击 PRO 算法 可以参考一下，稍微改一下就能满足你这个需求

[chairuosen]

count%2===0?A:B

[whosesmile]

你可以设置一个奖品数组：P = [A,B,C,D]，然后用随机数选取 [0 - length)，选到了就将对应的奖品移除，重置 P 值

上面是假定每个奖品只有一个，如果你有 500 个 A ，500 个 B ，类似的处理为:
P = [{A:500}, {B:500}]，每次随机 [0, length)，然后将对应的奖品数 -1,当触发临界值即 0 时，同样移除，重置 PP

[whosesmile]

@whosesmile 抽奖程序如果有并发，肯定要同步锁哈，不然数据对不上；然后 P 的初始化，或者重建，通过库存确定就行了。

[whileFalse]

有那么难吗...
if random()*(a_remain + b_remain) < a_remain
then
a_remain --
print("A")
else
b_remain --
print("B")

[leonshaw]

算出前面已经抽出的每种奖品频率，取目标概率减频率最大的那个

[sillydaddy]

不要改，拿概率论怼给他：

投掷 1000 次硬币，标准差是 sqrt(1000*0.5*0.5)=15.8 ，那么投掷出正面次数与 500 次之差在 1 个标准差之内的概率大概是 68%，在 2 个标准差之内的概率大概是 95%，在 3 个标准差之内的概率大概是 99.7%。

具体可以看下面这个正态分布图：
https://www.shuxuele.com/data/standard-normal-distribution-table.html

你给的结果，正好卡在 1 个标准差那条线上，是非常正常的情况。如果是 3 个标准差，那么结果就是 A 或 B 抽中 530 ，B 或 A 抽中 440 ，出现类似这种情况的概率大概是 0.3%。
所以不要那么弱势！！

[sillydaddy]

@sillydaddy 我在上面的回复有点武断。

今天又思考了一下这个问题，发现有一个很简单的方法，就是增加抽奖的次数。比如你想抽 1000 次分配给 A 和 B ，但觉得抽 1000 次的标准差(你说的误差)太大，那就可以抽 10000 次，然后用 10000 次抽奖的最终结果除以 10 。比如 10000 次里面 A 得 5050 次，B 得 4950 ，分别除以 10 ，得到 A 得 505 次，B 得 495 次。为什么举这个数字呢，因为投掷 10000 次硬币，标准差就是 50 。相比投掷 1000 次时的标准差 15 ，并不是增大到 10 倍，而是只有 3 倍左右。

除以 10 这个操作，相当于把标准正态分布的图像在 x 轴方向上压扁了，然后在 1 个标准差内的概率就增大了。如果想实时显示抽奖过程，那就累积 A 或 B 的中奖次数，每累积到 10 次，就算作真实中奖 1 次。当抽完 10000 次，A 和 B 真实中奖总次数就是 1000 次。