微信抢红包分配算法

最近工作上又一个需求是对一个数字进行随机分段,这个需求很像是微信抢红包的模型。在网上简单看了看,主要有以下两种方法,记录一下,其中第二种方法和我一开始的思路比较一致,后面选择的也是第二个。

二倍均值法

假设剩余红包金额为m,剩余人数为n,那么有以下等式:

每次抢到的红包 = 随机区间(0, m/n * 2)

比如:

假设有十个人分红包,红包总额为100元,第一个人抢到的金额范围为(0, 100/10 * 2),平均期望为10 元;第二个人抢到的金额范围为(0, 90/9 * 2),平均也是10元。以此类推到第十个人也是10元。那么代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void average(int m, int n)
{
int remainValue= m;
int remainCount = n;
int value = 0;
for(int i = 0; i < n; ++i){
if(1 >= remainCount){
value = remainValue;
} else{
//此处做一个简化,最少能抢到1元,如果做成浮点数对应放大即可
//randBetween是我自己实现的随机函数,[low, high]两边都是闭区间,所以这种写法并不完全符合这个思想因为最后一个人会比期望多一些。此处自行理解改进即可
value = CTS::randBetween(1, remainValue / (n - i) - 1);
}

remainValue -= value;
--remainCount;
std::cout << "no." << i + 1 << " get " << value << " remain value " << remainValue << std::endl;
}
}

结果如下:

我们可以看到,虽然说期望是平均值,但其实结果还是有一定差异的(即使除去我以为随机函数导致的差异还是很大)。

线段分割法

我们可以把总数想成是一个线段,那么如果要随机分出n端来,就只需要找出n-1个不重复的点来切割就可以了。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void cutLine(int m, int n)
{
int32 total = m;

std::vector<int32> line;
std::vector<int32> result;
std::set<int32> allPoint;
bool pardon = true;

if(total > 0){
for(int i = 0 ; i < n - 1; ++i){
if(pardon){
int32 index = CTS::randBetween(1, total - 1);
allPoint.insert(index);
} else{
do{
int32 index = CTS::randBetween(1, total);
if(allPoint.find(index) == allPoint.end()){
allPoint.insert(index);
break;
}
}while(1);
}
}
}

line.push_back(0);
for(auto it: allPoint){
line.push_back(it);
}
line.push_back(total);

for(int32 i = 0; i < line.size() - 1; ++i){
result.push_back(line[i + 1] - line[i]);
}
//不足部分补0
for(int32 i = result.size(); i < n; ++i){
result.push_back(0);
}

CTS::printfVec(line);
CTS::printfVec(result);
}

结果如下:

第一个是total为0的情况,这点需要注意一下,要不然会出现一对1和-1。第一个数组是切割点位置,包括0点和total终点;第二个数组就是n个切割出来的值了。

总结

两种方法我工作上最终选择了线段分割法,直觉上感觉这种方法更随机一些。但我这种写法消耗的时间和空间都更大(并不是指这种思路)。不过由于该子方法是一个不算很频繁的逻辑功能调用,暂且可以如此。如果后续觉得不太好,也可以进行优化掉。

最后说到微信红包,我在网上浏览文章时,发现有两种说法。

一是一些人做出大量测试,结果很偏向微信红包使用的是二倍均值法

二是说微信红包用的是一种更复杂的方法,详细参见这篇文章微信红包的随机算法是怎样实现的?