一种红包分配算法及其实现

该算法适用于多人抢红包的场景，可动态调整红包分配金额的平均程度。红包余额需大于红包剩余份数，分配的金额为整数，如果需要分配成小数，将红包余额乘以100，分配结果除以100即可。

算法概述

红包余额R，红包剩余份数D，方差因子VF（>=0），分配金额G，每一份的最小金额为min

  1. D=1，则G=R
  2. D>1，按(R/D) + random(-(R/D)*VF, (R/D)*VF)将R循环分解为一个含有D个元素的列表，
    random方法取[a,b]范围的随机值。元素的值如果小于min，则取min，同时元素有一个动态的最大
    值max，保证后续元素的值均不小于min
  3. 从第2步得到的列表中随机选择一个元素作为G

容易看出

  • VF取0时，每个人分配到的金额都是R/D
  • VF的值越大，出现最小额度的概率越大，分配额度序列的方差越大（取为1较合理）
  • 第3步使得分配金额与抢红包的先后顺序无关

Python实现

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
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

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
$ 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]