未来索引
开启左侧

微信红包的随机算法是怎样实现的?

[复制链接]
邢远 发表于 2015-2-15 04:57:27 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
微信红包的随机算法是怎样实现的?

RT。我考虑了一个简单的算法:
比如100元,由10个人分,那么平均一个人是10元钱。然后付款后,系统开始分份儿。
第一份:系统由0~10元之间随机一个数,作为这一份的钱数,设x1。
第二份:剩下的钱(100-x1),系统由0~(100-x1)/(10-1)随机一个数,作为这份的钱数,设x2
.。。。
第n份:剩下的钱(100-x1-x2-...-xn),系统由0~(100-x1-x2-...-xn-1)/(10-n)随机一个数,作为这个份的钱数,设为xn

当用户进来拿红包的时候,系统由0~9之间随机一个数,随机到几,就取第几份红包,然后将这个数存到list里。当之后的用户抽到相同的随机数时,则将这个数+1,如遇相同再+1,直至list满,红包发完。


InnerNight,非典型码农

我觉得这个问题的合理解有两个目标:1. 不要出现人为的阈值,比如预留值、最大和最少量、切割比例等拍脑袋的数据。2.尽量贴近过年的喜庆气氛,不要出现太多或者太少的情况。如果有什么其它考虑,方便实现成代码也算一个。
所以我的思路其实用一句话就可以概括:生成n(n是总人数)个(0,1]之间的随机数,然后将其求和被Q(Q是总钱数)除得到一个比例C,用C乘以所有数,这样就得到了最终结果。
这个算法很多人都会想到,但是被大家抛弃的原因应该在于随机性太大。那么我想到的修正方案:生成随机数时不要采用平均分布的随机数,而用正态分布的随机数。可是系统提供的随机数算法基本都是基于平均分布的,那现在提供一个平均分布映射到正态分布的算法就可以了。其实这个算法很常见,假设生成的平均分布数是x,正态分布所求值是y,正太分布表达式是f(y),那么f(y)求积分记为F(y),根据这样一个式子F(y) = x,求出F(y)的反函数就是所需要的映射函数。这个看起来很复杂,其实求出一个式子后代码写起来很简单。原谅我的数学表达基本已经都忘了,如果有写错,欢迎指正。
所以这个算法只需要两个function就可以实现,下面是个伪代码 :
double generateRandomNumber(){
//generate random number based on normal distribution
}

void process(double totalMoney, int personNum){
double[personNum] results;
for (int i=0; i < personNum; i++){
results = generateRandomNumber();
}
double ratio = totoalMoney/sum(results);
for (int i=0; i < personNum; i++){
results = result * ratio;
}
}

PS:这个算法的生产随机数其实是可配置的,取决于开发者希望最终趋近于什么样的分布,只要找到其和平均分布的映射关系,就可以使用什么样的生成算法。
PPS:这个分布算法如果能让用户配置会更好玩,比如配置成1个人领50%,3个人领30%,剩下的人分20%,还会有抽大奖的感觉,哈哈哈~


知乎用户,百科全书索引/DBA/缺睡
我们昨天几个人讨论了一晚上。
题主算法的问题是,有可能有一个人一下子把所有钱拿走了,而其他人都没有得到钱。
然后按照我对现在发出去和别人发的红包的观察,认为算法应该满足以下几个条件:
1、不能一个人一下子把钱拿走,也就是有预留额;
2、一个人拿到极小数(比如0.01元)的概率远大于拿到极大数(99%的总额)的概率;
3、多数人都是在平均数附近浮动的。
为了满足这几个条件,我提出一个算法假设:
1、使用偏正态分布产生各个红包;
2、有人为的红包上限设置,也即最大的红包不超过平均值的k倍,k的数值与红包个数n有关,同时也受到红包平均数money/n这个绝对值的制约;
采用这个算法的话,获得的红包同现在的情况比较符合。但是对于算法的第二点,我还无法做出更好的猜测,因为本人和朋友发红包的数量不多,无法做出基于大样本的猜测。





王霄池,连快排都得换成 Haskell 才能背下来的战…
据观察,红包分钱满足以下几点:
  • 不会有人拿不到钱
  • 不会提前分完
  • 钱的波动范围很大

@于野 的答案我完全同意。红包在一开始创建的时候,分配方案就订好了。抢红包的时候,不过是挨个pop up而已。

针对他说的算法二写个python代码。

def weixin_divide_hongbao(money, n):    divide_table = [random.randint(1, 10000) for x in xrange(0, n)]    sum_ = sum(divide_table)    return [x*money/sum_ for x in divide_table]

不过上述算法还有两个小问题:
  • 浮点数精度问题
  • 边界值的处理

不过,都是很容易解决的小问题,你们看的是算法思想,对吧。


匿名用户
1.一个随机算法。
2.计算第N个人的时候,要把前面N-1的人都抠出去。
3.计算第N个人的时候,要为后面的人预留出最低金额的总额,比如、每个人一分钱。
4.如果是最后一个人,那就不用算了,剩下的都是他的。

至于领取时,怎么把用户和金额关联起来,实现起来就自由了,对锁的依赖越少越好。


zhao alfred,斌哥

<meta charset="utf-8"><?php// 新年红包金额拆分试玩class CBonus{    public $bonus;//红包    public $bonus_num;//红包个数    public $bonus_money;//红包总金额    public $money_single_max;//单个红包限额        public function __construct(){        $this->bonus_num = 10;        $this->bonus_money = 200;        $this->money_single_max = 60;    }    private function randomFloat($min = 0, $max = 1) {        $mt_rand = mt_rand();        $mt_getrandmax = mt_getrandmax();        echo 'mt_rand=' . $mt_rand . ', mt_getrandmax=' . $mt_getrandmax . '<hr/>';        return $min + $mt_rand / $mt_getrandmax * ($max - $min);    }    //计算    public function compute()    {        $this->bonus = array();        $bonus_money_temp = $this->bonus_money;        $money_single_max = $this->money_single_max;        $i = 1;        while($i < $this->bonus_num)        {            if ($money_single_max > $bonus_money_temp)            {                $money_single_max = floatval(sprintf("%01.2f", $bonus_money_temp / 2));//剩余金额不够分时,把剩余金额的一半作为备用金            }            $bonus_money_rad = $this->randomFloat(0.01, $money_single_max);//一个红包随机金额 最小的1分钱            $bonus_money_rad = floatval(sprintf("%01.2f", $bonus_money_rad));            $bonus_money_temp = $bonus_money_temp - $bonus_money_rad ;//待分配的总剩余金额            $bonus_money_temp = floatval(sprintf("%01.2f", $bonus_money_temp));            $this->bonus[] = $bonus_money_rad;            //echo $bonus_money_rad . ',' . $bonus_money_temp . '<hr/>';            $i++;        }        $this->bonus[] = $bonus_money_temp;//分配剩余金额给最后一个红包    }    //打印    public function output(){        $total = 0;        foreach($this->bonus as $k => $v)        {            echo '红包' . ($k+1) . '=' . $v . '<br/>';            $total += $v;        }        echo '红包总金额:'.$total;    }}$CBonus = new CBonus();$CBonus->compute();$CBonus->output();?>
演示结果:
红包1=12.36
红包2=24.37
红包3=42.71
红包4=36.92
红包5=25.84
红包6=23.17
红包7=15.92
红包8=1.35
红包9=7.75
红包10=9.61
红包总金额:200
红包1=24.59
红包2=17.66
红包3=29.67
红包4=32.34
红包5=12.67
红包6=37.15
红包7=17.41
红包8=15.23
红包9=6.13
红包10=7.15
红包总金额:200
张晓,非典型IT男
目前观察到的情况来看,用户获取的红包钱数是会存在比较大的波动的。但我觉得不可能是初始时进行的划分,因为这样在红包初始生成时,计算量不可估计(发送红包的数量未加限制)。
我觉得,应该类似于是获得红包时,根据红包剩余金额和个数进行计算:
1、预留剩余的最小值 0.01*(n-1),并计算剩余钱的平均红包金额
2、生成随机数,再将本随机数取对数(目的在于使随机到小额度的可能性更大)
3、将对数结果乘以平均红包金额,再四舍五入,获得最后的钱数
4、线型计算,每次取红包计算时加锁


匿名用户
比如分给N个人。
出N个数的随机数列{A1,A2,...An},加起来归一化之后就可以得到每份红包的占比,再乘以总数就得到了N分随机红包。


红城米可,完美主义者,数字时代的手工艺人

我觉得就是一个设置了上下限的正态分布吧,用平均分布实现起来应该是最简单的了。

具体方法是上界是「0.01 / 金额总数」,上界是「(金额总数 - 0.01 * 人数) / 金额总数」,期望可以是「(上界 - 下界) / 人数」,方差的大小估计会考虑人的心理,然后产生「人数」个分布,用前「人数 - 1」个值乘以金额总数获得「人数 - 1」个红包大小,最后一个金额数由总金额减去前面的数字得到。完全没有必要动态生成,存储也很简单。

有人有大量的观察值可以否定这个假设吗?


dd zhang
我觉得比较简单的实现应该是这样的。
假设要发的红包金额是money,红包个数为n.
1.则生成n个随机正数Rand,对于1到n-1个红包则编号为k的人发到的红包金额:money*Rand_k/(Rand_0+Rand_1+…+Rand_(k-1))。(要避免单个红包金额过大或者过小,每个随机数Rand_k+基数x0)
2考虑到发出红包金额等于收到红包的金额,以及数据保留长度,最后一个红包是发出红包金额减去前面n-1个红包的金额


孙权,dream will come true。

保证后面的红包有钱最少金额n-i)*minBag , 当前能够划进红包的最大金额为:money-(n-i)*minBag,我们可以把这个最大值除以剩余的人数,作为当前可装进红包的最大值。这样可以实现则个效果~
98d9ea5c7e55c2f41b3dd4721de07717_b.jpg

E Books,CS PhD@HUST
核心算法就是随机数
主要的需求是得出10个红包,同时有一个隐性条件,每个红包中都要有钱,即每个红包至少1分钱。
如果是我会这么干(100块分成10个红包)
先取10分钱出来,这样可以屏蔽有的红包没钱的问题。剩下9990分钱,把这9990分钱分成10份即可。9990分钱一字排开,用9块板子插到这些钱中间(插板子这事你们肯定都干过),每两块板子中有多少钱就是一个红包中的钱数了,再加上之前取出的1分钱就是最后的红包了。怎么找插板子的位置呢?取0到1之间的随机数乘9991就好了,重复做9次。第1块板之前的钱加1分就是第一个红包里的钱数,依此类推得出10个红包中的钱数。
之后要测试这种方法是不是平均的分了。分个一万次,嗯,反正电脑不会累。回答完毕。
P.S.微信的红包表现还挺好的 也就卡个10来分钟。。。想发的可以先塞钱,过10分钟再发











该会员没有填写今日想说内容.

精彩评论1

wingsky110 发表于 2017-4-13 10:44:44 | 显示全部楼层
高手 有没有联系方式 加我QQ2929518997  有事请教
智能技术共享平台 - 未来论 http://www.mywll.com/
回复

使用道具 举报

高级模式
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关注2973

粉丝3237

帖子9934

发布主题
阅读排行 更多
广告位
!jz_fbzt! !jz_sgzt! !jz_xgzt! 快速回复 !jz_sctz! !jz_fhlb! 搜索

智能技术共享平台 - 未来论

关注服务号

进入小程序

全国服务中心:

运维中心:天津

未来之家:天津 青岛 济南 郑州 石家庄

                商务邮箱:xy@mywll.com

Copyright © 2012-2021 未来派 未来论 (津ICP备16000236号-5)