这是一个创建于 3062 天前的主题，其中的信息可能已经有所发展或是发生改变。
微信抢红包大家都很熟悉。
现在考虑这样一种情况：将 100 元的红包分为 10 份，每份最低 5 元最高 15 元，金额精确到 0.01 元。那么如果算法没问题的话，每个人的期望值自然是平均值，即 100 元 /10 人=10 元 /人。
最先想到的算法:
在 5~15 内生成随机数，即为当前用户的红包值。这种方式会出现分配后余额不足以按要求继续分配（剩余过多或过少）的情况，导致之后的红包内容均为最大值或最小值。这似乎也是微信红包的算法。
后来考虑了一种避免后期红包数值统一于极值的方式:
根据红包总份数 N 生成 N 个 0~1 内的随机数，按照各随机数在这些随机数之和中所占的比重，分配可分配的那部分金额（总金额 - 最小值 * 份数）。当出现不符合分配要求的情况时，对已求得的每个随机数进行求根运算(也可以是其他运算，只要减小方差就行)并重新求和。（代价是必须一次性得出所有红包的分配方案）
然后问题来了:
我统计了上述两种方法都结果，均没有出现众数集中在平均值的结果：
算法 1:
算法 2:
按我的理解，众数应当接近于期望值才比较理想。求大神指导下问题所在，以及有没有更好的算法
第 1 条附言 · 2016-07-25 00:43:51 +08:00
说明一下，图中数据是在 100 元分成 10 份，每份 6 到 12 元的条件下做的
第 2 条附言 · 2016-07-26 12:42:12 +08:00
研究了下正态分布，算是比较理想地解决了，贴一下算法：
function normalDistributionRandom() {
var v = 12;
var sum = 0, i = 0;
while (i++ < v) {
sum += Math.random();
}
return sum / v - 1 / 2; // -1/2 ~ 1/2
}
function (total, people, min, max) {
if (people * min > total || people * max < total) return false;
var sum = 0, lucks = [], luck;
var avg = total / people;
var i = 0;
while (i++ < people) {
do {
if (i === people) {
luck = total - sum;
break;
}
luck = avg + normalDistributionRandom() * (max - min);
} while (min > luck || max < luck || total - sum - luck < (people - i) * min || total - sum - luck > (people - i) * max);
lucks.push(luck);
sum += luck;
}
return lucks.map(function (cur) {
return cur.toFixed(2);
});
}
6~12元，平均10元/人的10000次统计：
至于怎么样让这条曲线两边再高一点，提高最值的概率，以后再折腾
 |
1
billlee 2016-07-25 01:18:59 +08:00
什么叫做众数集中在平均值？你是想说正太分布吗？
|
 |
2
aprikyblue 2016-07-25 01:49:46 +08:00 via Android
是想说萝莉分布吗:doge:
|
 |
3
HypoChen 2016-07-25 02:01:23 +08:00
我有一个方案，和你的方案二差不多，不过我不知道众数会在哪 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 ``` |
 |
4
Valyrian 2016-07-25 02:09:14 +08:00 via iPad
Google 搜索：排列组合 插板法
|
 |
5
3dwelcome 2016-07-25 02:23:37 +08:00 via Android
还是第一种算法、只是把最后那个人多出来的钱平摊到每个人头上既可。
比如生成 10 次六元到十二元的随机数、加起来如果是 110 不是 100 、那么每个人的红包都按照比例少拿 1 块。也就不存在最后一个人抽到太多或太少的情况、因为都被前面九个人均摊了。 |
 |
6
debiann 2016-07-25 08:17:10 +08:00 via iPhone  2
每人先拿 5 元，剩下 5000 个一分随机分发，拿满 15 封顶
|
 |
7
Exin OP @billlee 不仅仅是正太分布，算法 2 的结果也算是一种正态分布吧？
@aprikyblue @HypoChen 用的是 Google charts @debiann 这样算是不是会很费时？要给每个 1 分做一次循环？ |
|
11
Exin OP @debiann
我写了一下，结果如图  如果是 5 ～ 15 元，平均每人 10 元的条件，这个算法是比较理想的。 但是在图中 6 ～ 12 元，平均每人 10 元的条件下暴露了缺陷： 以期望值为中心正态分布，仅适用于最大值、最小值的平均值等于期望值的情况。 |
 |
12
imdoge 2016-07-25 11:09:43 +08:00
我的想法：每人先拿 5 元
剩下 50 元，随机生成 0~10 的随机数，剩余金额再随机 0~x ， x 是 min(10, 剩余金额) |
|
13
imdoge 2016-07-25 11:10:54 +08:00
重复 10 次……
|
|
15
3dwelcome 2016-07-25 11:21:33 +08:00
我来贴一下结果，用 100 元分十份，每份 7 元～ 13 元随机分布。循环很多次，然后绘图统计每个人拿到钱的概率。
 |
 |
16
Asimov 2016-07-25 11:30:43 +08:00
⎝≧⏝⏝≦⎠ 这么简单的问题被你描述的那么复杂。
|
|
20
Exin OP @3dwelcome 因为(13 + 7) / 2 = 10 ，(15 + 2) / 2 = 10 ，都是很简单的情况。我真正考虑的是两侧不均衡的条件下的算法。
|
|
21
3dwelcome 2016-07-25 11:48:40 +08:00
需要的话，我可以把程序贴上来，虽然是 c++写的。
如果你做了平均分配步骤的话，那形成图案，应该是特有的摆尾现象。原理就是 10 份 7 元～ 13 元的红包，总有加起来超过 100 元的时候，这时候会进行在再分配，两个顶端就会向中间移动。（比如：原来让 7 元或 13 元的，会变成 6.9 元或者 12.9 元， 7 元整数的概率，自然就少了，中间的概率，自然就多了） |
 |
23
alex321 2016-07-25 11:58:15 +08:00
不是程序猿的也来凑热闹。
我会先每人分 5 元，保证最低金额。然后还剩下 50 软妹币，也就是 5000 分，这个时候开始正式抽奖模式。方法是， 5000 分 10 人抽，只有一个抽奖规则，就是抽了超过 1000 的时候无效，奖金返回奖池重新抽。 |
|
24
3dwelcome 2016-07-25 12:00:58 +08:00
100 元， 10 人， 6 ～ 12 元条件。
图案看起来的确不太美观，几乎没有能拿到 6 元～ 7.5 元的概率。好吧，我想简单了-_-  |
|
26
alex321 2016-07-25 12:16:54 +08:00
@Exin 一定要纠结这个问题啊。。。那就改下规则了呃。比如 6-12 的话，限定先拿 6 软妹币，剩下的 4000 分 10 次抽，当抽取金额超过 600 的话返回奖池重抽。
我不是程序猿，刚才花一分钟写了个 demo 。。。。。吃饭去。 |
|
27
Exin OP @alex321 仅仅就你提到的内容来说的话，这样还是存在二次分配的问题，比如前几份都拿到 0 元，后面的就分不完了，需要再次分配。如何处理第二次分配是重点。
|
|
28
alex321 2016-07-25 13:18:05 +08:00
哦。你要的其实就是不管怎么样，始终那个峰值是在 10 附近。。
我这个时候一般会这么想，如果技术开发的同志能在 2h 内搞定算法，我没所谓，你爱钻研折腾是极好的；如果超过 2h ，那么就别忙活了，用简单的上吧。前台在页面上配合下，如果单单就说 100 元 10 人抽的话，用户心理预期是在每人 10 软妹币；那么换个说法，每人可以抽到 6 到 16 不等的金额哦，那么用户的心理预期就不会是 10 了，可能是 16 了。 总的来说，产品功能实现需要花费的精力也是有预算的，当过于追求完美花费代价太大的时候，我会接受 80% 甚至 60% 的完美程度。 |
 |
30
Vizogood 2016-07-25 13:52:32 +08:00 via Android
知乎上原来见过这个问题，有一句话，你们考虑了那么多，却没考虑到实际操作时服务器的承受能力。所以最有可能是，最简单的一种
随机分配即可满足。 |
|
32
alex321 2016-07-25 14:18:02 +08:00
真要这么样的话，在 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 |
|
33
3dwelcome 2016-07-25 14:44:04 +08:00
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); } // 注，代码用到了高斯随机数，用普通的随机数替换，绘制出的图形，也是类似的，中间高，两头低。如下:  |
|
35
3dwelcome 2016-07-25 17:32:36 +08:00 via Android
啥是边界呀、把 100 元全部分配完了啊。
|
|
36
Exin OP @3dwelcome 比如 array[0]随机得到了 12.0 元， array[1...n]的总和小于总金额，于是会进入第三个 for 循环，将剩余金额的 1/10 加到了 12 上。于是就越过了金额限制边界 12 。
|
 |
37
cszhiyue 2016-07-25 20:35:38 +08:00
|
|
38
cszhiyue 2016-07-25 20:36:42 +08:00
 |
|
39
cszhiyue 2016-07-25 20:39:50 +08:00 1
|
|
40
Exin OP @cszhiyue
好吧我仔细看了看……哥们你代码不太对吧…… 首先从图形上来说，这是大概一个以 10 为中心左右对称的曲线，那么这个曲线所代表的数值的平均值显然是小于 10 的，因为右边缺了一块。 再从算法上说，我随便跑了几次， generate_red_packets 返回的 list 求和根本就不是 100.00 您再仔细看看？ |
|
42
Exin OP |
 |
43
RqPS6rhmP3Nyn3Tm 2016-07-26 02:41:45 +08:00 via Android
这不就是正态分布图吧
|
Select Language