关于红包算法的问题

[Exin]

微信抢红包大家都很熟悉。

现在考虑这样一种情况：将 100 元的红包分为 10 份，每份最低 5 元最高 15 元，金额精确到 0.01 元。那么如果算法没问题的话，每个人的期望值自然是平均值，即 100 元 /10 人=10 元 /人。

最先想到的算法:

在 5~15 内生成随机数，即为当前用户的红包值。这种方式会出现分配后余额不足以按要求继续分配（剩余过多或过少）的情况，导致之后的红包内容均为最大值或最小值。这似乎也是微信红包的算法。

后来考虑了一种避免后期红包数值统一于极值的方式:

根据红包总份数 N 生成 N 个 0~1 内的随机数，按照各随机数在这些随机数之和中所占的比重，分配可分配的那部分金额（总金额 - 最小值 * 份数）。当出现不符合分配要求的情况时，对已求得的每个随机数进行求根运算(也可以是其他运算，只要减小方差就行)并重新求和。（代价是必须一次性得出所有红包的分配方案）

然后问题来了:

我统计了上述两种方法都结果，均没有出现众数集中在平均值的结果：

算法 1:

算法 2:

按我的理解，众数应当接近于期望值才比较理想。求大神指导下问题所在，以及有没有更好的算法

[billlee]

什么叫做众数集中在平均值？你是想说正太分布吗？

[aprikyblue]

是想说萝莉分布吗:doge:

[HypoChen]

我有一个方案，和你的方案二差不多，不过我不知道众数会在哪 23333 ，想问你怎么画的图 23333

```
def comp(sum=100, n=10):
result = []
while n > 1:
min = sum - 15 * (n - 1) if sum - 15 * (n - 1) >= 5 else 5
max = sum - 5 * (n-1) if sum - 5 * (n-1) <= 15 else 15
rand = random.uniform(min, max)
rand = round(rand, 2)
result.append(rand)
sum -= rand
n -= 1
result.append(round(sum, 2))
return result
```

[Valyrian]

Google 搜索：排列组合 插板法

[3dwelcome]

还是第一种算法、只是把最后那个人多出来的钱平摊到每个人头上既可。

比如生成 10 次六元到十二元的随机数、加起来如果是 110 不是 100 、那么每个人的红包都按照比例少拿 1 块。也就不存在最后一个人抽到太多或太少的情况、因为都被前面九个人均摊了。

[debiann]

每人先拿 5 元，剩下 5000 个一分随机分发，拿满 15 封顶

[Exin]

@billlee 不仅仅是正太分布，算法 2 的结果也算是一种正态分布吧？
@aprikyblue

@HypoChen 用的是 Google charts

@debiann 这样算是不是会很费时？要给每个 1 分做一次循环？

[Exin]

@HypoChen 你的算法应该是和我的方案一 一样的吧，只是每次界定分配金额的时间点不同

[Exin]

@3dwelcome 也考虑过这种方法，以为效果不佳就没去写。刚刚写了一下，结果比较惊喜，我贴在 Append 里了。

[Exin]

@3dwelcome 贴之前仔细看了看，是我写错了……还是贴一下结果：

[Exin]

@debiann
我写了一下，结果如图


如果是 5 ～ 15 元，平均每人 10 元的条件，这个算法是比较理想的。
但是在图中 6 ～ 12 元，平均每人 10 元的条件下暴露了缺陷：
以期望值为中心正态分布，仅适用于最大值、最小值的平均值等于期望值的情况。

[imdoge]

我的想法：每人先拿 5 元
剩下 50 元，随机生成 0~10 的随机数，剩余金额再随机 0~x ， x 是 min(10, 剩余金额)

[imdoge]

重复 10 次……

[Exin]

@imdoge 这和我的算法 1 、 3L 的算法，有什么区别吗？

[3dwelcome]

我来贴一下结果，用 100 元分十份，每份 7 元～ 13 元随机分布。循环很多次，然后绘图统计每个人拿到钱的概率。

[Asimov]

⎝≧⏝⏝≦⎠ 这么简单的问题被你描述的那么复杂。

[Exin]

@Valyrian 对于单份金额上下限的限制，插板法中该如何处理呢？

[Exin]

@Asimov 那麻烦你说一下优秀的解法？

[Exin]

@3dwelcome 能否贴一下 100 元， 10 人， 6 ～ 12 元条件下的结果？

[Exin]

@3dwelcome 因为(13 + 7) / 2 = 10 ，(15 + 2) / 2 = 10 ，都是很简单的情况。我真正考虑的是两侧不均衡的条件下的算法。