V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Exin
V2EX  ›  问与答

关于红包算法的问题

  •  
  •   Exin · 2016-07-24 23:28:39 +08:00 · 3549 次点击
    这是一个创建于 3042 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    现在考虑这样一种情况:将 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次统计:

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

    44 条回复    2016-07-26 10:44:59 +08:00
    billlee
        1
    billlee  
       2016-07-25 01:18:59 +08:00
    什么叫做众数集中在平均值?你是想说正太分布吗?
    aprikyblue
        2
    aprikyblue  
       2016-07-25 01:49:46 +08:00 via Android
    是想说萝莉分布吗:doge:
    HypoChen
        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
    ```
    Valyrian
        4
    Valyrian  
       2016-07-25 02:09:14 +08:00 via iPad
    Google 搜索:排列组合 插板法
    3dwelcome
        5
    3dwelcome  
       2016-07-25 02:23:37 +08:00 via Android
    还是第一种算法、只是把最后那个人多出来的钱平摊到每个人头上既可。

    比如生成 10 次六元到十二元的随机数、加起来如果是 110 不是 100 、那么每个人的红包都按照比例少拿 1 块。也就不存在最后一个人抽到太多或太少的情况、因为都被前面九个人均摊了。
    debiann
        6
    debiann  
       2016-07-25 08:17:10 +08:00 via iPhone   ❤️ 2
    每人先拿 5 元,剩下 5000 个一分随机分发,拿满 15 封顶
    Exin
        7
    Exin  
    OP
       2016-07-25 10:12:42 +08:00 via Android
    @billlee 不仅仅是正太分布,算法 2 的结果也算是一种正态分布吧?
    @aprikyblue

    @HypoChen 用的是 Google charts

    @debiann 这样算是不是会很费时?要给每个 1 分做一次循环?
    Exin
        8
    Exin  
    OP
       2016-07-25 10:18:23 +08:00
    @HypoChen 你的算法应该是和我的方案一 一样的吧,只是每次界定分配金额的时间点不同
    Exin
        9
    Exin  
    OP
       2016-07-25 10:42:32 +08:00
    @3dwelcome 也考虑过这种方法,以为效果不佳就没去写。刚刚写了一下,结果比较惊喜,我贴在 Append 里了。
    Exin
        10
    Exin  
    OP
       2016-07-25 10:50:28 +08:00
    @3dwelcome 贴之前仔细看了看,是我写错了……还是贴一下结果:
    Exin
        11
    Exin  
    OP
       2016-07-25 11:06:38 +08:00
    @debiann
    我写了一下,结果如图


    如果是 5 ~ 15 元,平均每人 10 元的条件,这个算法是比较理想的。
    但是在图中 6 ~ 12 元,平均每人 10 元的条件下暴露了缺陷:
    以期望值为中心正态分布,仅适用于最大值、最小值的平均值等于期望值的情况。
    imdoge
        12
    imdoge  
       2016-07-25 11:09:43 +08:00
    我的想法:每人先拿 5 元
    剩下 50 元,随机生成 0~10 的随机数,剩余金额再随机 0~x , x 是 min(10, 剩余金额)
    imdoge
        13
    imdoge  
       2016-07-25 11:10:54 +08:00
    重复 10 次……
    Exin
        14
    Exin  
    OP
       2016-07-25 11:14:58 +08:00
    @imdoge 这和我的算法 1 、 3L 的算法,有什么区别吗?
    3dwelcome
        15
    3dwelcome  
       2016-07-25 11:21:33 +08:00
    我来贴一下结果,用 100 元分十份,每份 7 元~ 13 元随机分布。循环很多次,然后绘图统计每个人拿到钱的概率。

    Asimov
        16
    Asimov  
       2016-07-25 11:30:43 +08:00
    ⎝≧⏝⏝≦⎠ 这么简单的问题被你描述的那么复杂。
    Exin
        17
    Exin  
    OP
       2016-07-25 11:43:42 +08:00
    @Valyrian 对于单份金额上下限的限制,插板法中该如何处理呢?
    Exin
        18
    Exin  
    OP
       2016-07-25 11:44:19 +08:00
    @Asimov 那麻烦你说一下优秀的解法?
    Exin
        19
    Exin  
    OP
       2016-07-25 11:45:23 +08:00
    @3dwelcome 能否贴一下 100 元, 10 人, 6 ~ 12 元条件下的结果?
    Exin
        20
    Exin  
    OP
       2016-07-25 11:46:54 +08:00
    @3dwelcome 因为(13 + 7) / 2 = 10 ,(15 + 2) / 2 = 10 ,都是很简单的情况。我真正考虑的是两侧不均衡的条件下的算法。
    3dwelcome
        21
    3dwelcome  
       2016-07-25 11:48:40 +08:00
    需要的话,我可以把程序贴上来,虽然是 c++写的。

    如果你做了平均分配步骤的话,那形成图案,应该是特有的摆尾现象。原理就是 10 份 7 元~ 13 元的红包,总有加起来超过 100 元的时候,这时候会进行在再分配,两个顶端就会向中间移动。(比如:原来让 7 元或 13 元的,会变成 6.9 元或者 12.9 元, 7 元整数的概率,自然就少了,中间的概率,自然就多了)
    Exin
        22
    Exin  
    OP
       2016-07-25 11:52:18 +08:00
    @3dwelcome 麻烦你贴一下代码吧,因为我们的结果统计差别太大了,一定是哪里沟通有误
    alex321
        23
    alex321  
       2016-07-25 11:58:15 +08:00
    不是程序猿的也来凑热闹。

    我会先每人分 5 元,保证最低金额。然后还剩下 50 软妹币,也就是 5000 分,这个时候开始正式抽奖模式。方法是, 5000 分 10 人抽,只有一个抽奖规则,就是抽了超过 1000 的时候无效,奖金返回奖池重新抽。
    3dwelcome
        24
    3dwelcome  
       2016-07-25 12:00:58 +08:00
    100 元, 10 人, 6 ~ 12 元条件。

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

    Exin
        25
    Exin  
    OP
       2016-07-25 12:01:07 +08:00
    @alex321 6L 提到了这种方法,这种方法存在问题,详见 11L
    alex321
        26
    alex321  
       2016-07-25 12:16:54 +08:00
    @Exin 一定要纠结这个问题啊。。。那就改下规则了呃。比如 6-12 的话,限定先拿 6 软妹币,剩下的 4000 分 10 次抽,当抽取金额超过 600 的话返回奖池重抽。
    我不是程序猿,刚才花一分钟写了个 demo 。。。。。吃饭去。
    Exin
        27
    Exin  
    OP
       2016-07-25 12:43:58 +08:00
    @alex321 仅仅就你提到的内容来说的话,这样还是存在二次分配的问题,比如前几份都拿到 0 元,后面的就分不完了,需要再次分配。如何处理第二次分配是重点。
    alex321
        28
    alex321  
       2016-07-25 13:18:05 +08:00
    哦。你要的其实就是不管怎么样,始终那个峰值是在 10 附近。。
    我这个时候一般会这么想,如果技术开发的同志能在 2h 内搞定算法,我没所谓,你爱钻研折腾是极好的;如果超过 2h ,那么就别忙活了,用简单的上吧。前台在页面上配合下,如果单单就说 100 元 10 人抽的话,用户心理预期是在每人 10 软妹币;那么换个说法,每人可以抽到 6 到 16 不等的金额哦,那么用户的心理预期就不会是 10 了,可能是 16 了。
    总的来说,产品功能实现需要花费的精力也是有预算的,当过于追求完美花费代价太大的时候,我会接受 80% 甚至 60% 的完美程度。
    Exin
        29
    Exin  
    OP
       2016-07-25 13:49:32 +08:00
    @alex321 实际开发自然是不会这样的。我在这里提问主要是想看看有没有真正优秀的算法能实现这个需求。
    Vizogood
        30
    Vizogood  
       2016-07-25 13:52:32 +08:00 via Android
    知乎上原来见过这个问题,有一句话,你们考虑了那么多,却没考虑到实际操作时服务器的承受能力。所以最有可能是,最简单的一种
    随机分配即可满足。
    Exin
        31
    Exin  
    OP
       2016-07-25 13:57:16 +08:00
    @Vizogood 不考虑真要拿去分配红包的算法……不用考虑硬件限制。你想多了
    alex321
        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
    3dwelcome
        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);
    }


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

    Exin
        34
    Exin  
    OP
       2016-07-25 17:05:29 +08:00 via Android
    @3dwelcome 你这个算法...没有边界处理...
    3dwelcome
        35
    3dwelcome  
       2016-07-25 17:32:36 +08:00 via Android
    啥是边界呀、把 100 元全部分配完了啊。
    Exin
        36
    Exin  
    OP
       2016-07-25 18:33:01 +08:00
    @3dwelcome 比如 array[0]随机得到了 12.0 元, array[1...n]的总和小于总金额,于是会进入第三个 for 循环,将剩余金额的 1/10 加到了 12 上。于是就越过了金额限制边界 12 。
    cszhiyue
        37
    cszhiyue  
       2016-07-25 20:35:38 +08:00
    cszhiyue
        38
    cszhiyue  
       2016-07-25 20:36:42 +08:00
    cszhiyue
        39
    cszhiyue  
       2016-07-25 20:39:50 +08:00   ❤️ 1
    Exin
        40
    Exin  
    OP
       2016-07-25 21:36:53 +08:00
    @cszhiyue
    好吧我仔细看了看……哥们你代码不太对吧……
    首先从图形上来说,这是大概一个以 10 为中心左右对称的曲线,那么这个曲线所代表的数值的平均值显然是小于 10 的,因为右边缺了一块。
    再从算法上说,我随便跑了几次, generate_red_packets 返回的 list 求和根本就不是 100.00
    您再仔细看看?
    cszhiyue
        41
    cszhiyue  
       2016-07-25 23:23:15 +08:00
    @Exin 忽略了边界
    已经修正
    Exin
        42
    Exin  
    OP
       2016-07-26 00:20:32 +08:00
    @cszhiyue 谢谢
    你的算法最“特别”的地方在于用了高斯随机数,我一直在弄 0~1 均匀分布的随机因子,难怪想破头

    我该去看看如何实现高斯随机数了
    RqPS6rhmP3Nyn3Tm
        43
    RqPS6rhmP3Nyn3Tm  
       2016-07-26 02:41:45 +08:00 via Android
    这不就是正态分布图吧
    Exin
        44
    Exin  
    OP
       2016-07-26 10:44:59 +08:00 via Android
    @BXIA 正态分布是左右对称的吧,我想要的是不对称但平滑简单的曲线。 41L 的比较接近,但是最大那边的图形还是让我不太满意
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2758 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 12:48 · PVG 20:48 · LAX 04:48 · JFK 07:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.