该算法适用于多人抢红包的场景,可动态调整红包分配金额的平均程度。红包余额需大于红包剩余份数,分配的金额为整数,如果需要分配成小数,将红包余额乘以100,分配结果除以100即可。
算法概述
红包余额R,红包剩余份数D,方差因子VF(>=0),分配金额G,每一份的最小金额为min
- D=1,则G=R
- D>1,按(R/D) + random(-(R/D)*VF, (R/D)*VF)将R循环分解为一个含有D个元素的列表,random方法取[a,b]范围的随机值。元素的值如果小于min,则取min,同时元素有一个动态的最大值max,保证后续元素的值均不小于min
- 从第2步得到的列表中随机选择一个元素作为G
容易看出
- VF取0时,每个人分配到的金额都是R/D
- VF的值越大,出现最小额度的概率越大,分配额度序列的方差越大(取为1较合理)
- 第3步使得分配金额与抢红包的先后顺序无关
Python实现
import random
def avg(remain, dv):
return remain / dv
def randNoise(noise, expected = 0):
return random.randint(expected - noise, expected + noise)
def divideToList(remain, dv, vf, min):
divided = []
while dv > 0:
if dv == 1:
get = remain
else:
max = remain - (min * (dv-1))
av = avg(remain, dv)
get = av + randNoise(int(av * vf))
if get < min:
get = min
elif get > max:
get = max
divided.append(get)
dv = dv - 1
remain = remain - get
return divided
def assignToList(remain, dv, vf, min):
L = []
while dv > 0:
div = divideToList(remain, dv, vf, min)
g = random.choice(div)
L.append(g)
dv = dv-1
remain = remain - g
return L
测试代码
import sys
def testAssignment(L, dv):
if len(L) != dv:
print 'Bad #not average'
return False
for i in L:
if i <= 0:
print 'Bad #negative or zero'
return False
return True
remain = int(sys.argv[1])
dv = int(sys.argv[2])
vf = float(sys.argv[3])
min = int(sys.argv[4])
testTimes = int(sys.argv[5])
while testTimes > 0:
L = assignToList(remain, dv, vf, min)
if testAssignment(L, dv) == True:
print 'Good'
print L
testTimes = testTimes - 1
输出
$ python red_env.py 999 10 1.0 1 10
Good
[191, 114, 185, 122, 101, 23, 47, 8, 139, 69]
Good
[60, 41, 80, 139, 68, 30, 199, 268, 113, 1]
Good
[72, 149, 120, 143, 116, 12, 27, 154, 183, 23]
Good
[137, 180, 29, 120, 92, 26, 1, 249, 85, 80]
Good
[117, 118, 55, 69, 150, 151, 2, 34, 44, 259]
Good
[87, 7, 18, 88, 40, 9, 129, 334, 80, 207]
Good
[181, 125, 16, 69, 115, 9, 86, 179, 168, 51]
Good
[33, 55, 198, 183, 1, 209, 128, 83, 16, 93]
Good
[19, 55, 266, 234, 116, 60, 103, 50, 69, 27]
Good
[122, 85, 70, 10, 288, 127, 6, 98, 163, 30]