关于红包算法的问题

[Exin]

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

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

最先想到的算法:

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

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

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

然后问题来了:

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

算法 1:

算法 2:

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

说明一下，图中数据是在 100 元分成 10 份，每份 6 到 12 元的条件下做的

研究了下正态分布，算是比较理想地解决了，贴一下算法：

  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次统计：

至于怎么样让这条曲线两边再高一点，提高最值的概率，以后再折腾

[billlee]

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

[aprikyblue]

是想说萝莉分布吗:doge:

[Hyponet]

我有一个方案，和你的方案二差不多，不过我不知道众数会在哪 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 ，都是很简单的情况。我真正考虑的是两侧不均衡的条件下的算法。

[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
您再仔细看看？

[cszhiyue]

@Exin 忽略了边界
已经修正

[Exin]

@cszhiyue 谢谢
你的算法最“特别”的地方在于用了高斯随机数，我一直在弄 0~1 均匀分布的随机因子，难怪想破头

我该去看看如何实现高斯随机数了

[RqPS6rhmP3Nyn3Tm]

这不就是正态分布图吧

[Exin]

@BXIA 正态分布是左右对称的吧，我想要的是不对称但平滑简单的曲线。 41L 的比较接近，但是最大那边的图形还是让我不太满意