关于红包算法的问题

[Exin]

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

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

最先想到的算法:

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

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

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

然后问题来了:

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

算法 1:

算法 2:

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

[3dwelcome]

需要的话，我可以把程序贴上来，虽然是 c++写的。

如果你做了平均分配步骤的话，那形成图案，应该是特有的摆尾现象。原理就是 10 份 7 元～ 13 元的红包，总有加起来超过 100 元的时候，这时候会进行在再分配，两个顶端就会向中间移动。（比如：原来让 7 元或 13 元的，会变成 6.9 元或者 12.9 元， 7 元整数的概率，自然就少了，中间的概率，自然就多了）

[Exin]

@3dwelcome 麻烦你贴一下代码吧，因为我们的结果统计差别太大了，一定是哪里沟通有误

[alex321]

不是程序猿的也来凑热闹。

我会先每人分 5 元，保证最低金额。然后还剩下 50 软妹币，也就是 5000 分，这个时候开始正式抽奖模式。方法是， 5000 分 10 人抽，只有一个抽奖规则，就是抽了超过 1000 的时候无效，奖金返回奖池重新抽。

[3dwelcome]

100 元， 10 人， 6 ～ 12 元条件。

图案看起来的确不太美观，几乎没有能拿到 6 元～ 7.5 元的概率。好吧，我想简单了-_-

[Exin]

@alex321 6L 提到了这种方法，这种方法存在问题，详见 11L

[alex321]

@Exin 一定要纠结这个问题啊。。。那就改下规则了呃。比如 6-12 的话，限定先拿 6 软妹币，剩下的 4000 分 10 次抽，当抽取金额超过 600 的话返回奖池重抽。
我不是程序猿，刚才花一分钟写了个 demo 。。。。。吃饭去。

[Exin]

@alex321 仅仅就你提到的内容来说的话，这样还是存在二次分配的问题，比如前几份都拿到 0 元，后面的就分不完了，需要再次分配。如何处理第二次分配是重点。

[alex321]

哦。你要的其实就是不管怎么样，始终那个峰值是在 10 附近。。
我这个时候一般会这么想，如果技术开发的同志能在 2h 内搞定算法，我没所谓，你爱钻研折腾是极好的；如果超过 2h ，那么就别忙活了，用简单的上吧。前台在页面上配合下，如果单单就说 100 元 10 人抽的话，用户心理预期是在每人 10 软妹币；那么换个说法，每人可以抽到 6 到 16 不等的金额哦，那么用户的心理预期就不会是 10 了，可能是 16 了。
总的来说，产品功能实现需要花费的精力也是有预算的，当过于追求完美花费代价太大的时候，我会接受 80% 甚至 60% 的完美程度。

[Exin]

@alex321 实际开发自然是不会这样的。我在这里提问主要是想看看有没有真正优秀的算法能实现这个需求。

[Vizogood]

知乎上原来见过这个问题，有一句话，你们考虑了那么多，却没考虑到实际操作时服务器的承受能力。所以最有可能是，最简单的一种
随机分配即可满足。

[Exin]

@Vizogood 不考虑真要拿去分配红包的算法……不用考虑硬件限制。你想多了

[alex321]

真要这么样的话，在 10 那块做正态分布，然后按照你界定的红包金额最大和最小值，在这个区间里面去随机取样，按照 10 个一组，直到取出一组样本的金额数值之和为总金额的了呃。
https://zh.wikipedia.org/wiki/%E6%AD%A3%E6%80%81%E5%88%86%E5%B8%83#/media/File:Normal_approximation_to_binomial.png

[3dwelcome]

std::vector<int> partset;
partset.resize(512);

int i;
for (int n=0;n<5000;n++)
{
int array[10];
int count = 0;
for (i=0;i<10;i++)
{
int vv = randomGaussRange(60, 120); // 产生 6.0 元 - 12.0 元的高斯随机数
array[i] = vv;
count += vv;
}

for (i=0;i<10;i++) // 10 个人均分 100 元
{
array[i] += ((1000 - count)/10);
}

for (i=0;i<10;i++) // 累加统计每人得到的钱的分布概率, x=钱值， y=抽到的数量
{
int x = array[i];
int y = 0;

if (x < 0) x = 0;
if (x > 500)x = 500;
partset[x]++;
}
}

for (i=0;i<=60;i++) // 缩放绘制到屏幕
{
int x = 10+5 + i*6;
int y = 35 + CROP(partset[i+60]/10, 0, 200);

// drawcircle(x, y, _blue);
}


// 注，代码用到了高斯随机数，用普通的随机数替换，绘制出的图形，也是类似的，中间高，两头低。如下:

[Exin]

@3dwelcome 你这个算法...没有边界处理...

[3dwelcome]

啥是边界呀、把 100 元全部分配完了啊。

[Exin]

@3dwelcome 比如 array[0]随机得到了 12.0 元， array[1...n]的总和小于总金额，于是会进入第三个 for 循环，将剩余金额的 1/10 加到了 12 上。于是就越过了金额限制边界 12 。

[cszhiyue]

http://7xnq5e.com1.z0.glb.clouddn.com/2016-07-25-20-35-07.png

[cszhiyue]

[cszhiyue]

https://gist.github.com/zhiyue/956857ee78d2f7b06fd814c24d92ff5f

[Exin]

@cszhiyue
好吧我仔细看了看……哥们你代码不太对吧……
首先从图形上来说，这是大概一个以 10 为中心左右对称的曲线，那么这个曲线所代表的数值的平均值显然是小于 10 的，因为右边缺了一块。
再从算法上说，我随便跑了几次， generate_red_packets 返回的 list 求和根本就不是 100.00
您再仔细看看？