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

## 算法概述

1. D=1，G=R
2. D>1，按(R/D) + random(-(R/D)*N, (R/D)*N)将R分解为一个列表，random方法取[a,b]范围的随机值
3. 从第2步得到的列表中随机选择一个作为G

• N取0时，每个人分配到的金额相等，都是R/D（最后一份可能不等于该值）
• N取1时，可能出现分配金额为0的情况，所以N的取值应小于1
• N的值越大，分配金额的分布越不平均
• 第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, noiseRate):     divided = []     while dv > 0:         if dv == 1:             get = remain         else:             av = avg(remain, dv)             get = av + randNoise(int(av * noiseRate))         divided.append(get)         dv = dv - 1         remain = remain - get     return divided  def assignToList(remain, dv, noiseRate):     L = []     while dv > 0:         div = divideToList(remain, dv, noiseRate)         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]) noiseRate = float(sys.argv[3]) testTimes = int(sys.argv[4])  while testTimes > 0:     L = assignToList(remain, dv, noiseRate)     if testAssignment(L, dv) == True:         print 'Good'     print L     testTimes = testTimes - 1``

``# python red_env.py 500 10 0.9 10 Good [33, 94, 62, 9, 42, 39, 19, 77, 83, 42] Good [27, 38, 37, 133, 10, 48, 54, 113, 21, 19] Good [42, 84, 71, 61, 47, 51, 36, 59, 14, 35] Good [74, 38, 17, 94, 59, 65, 100, 8, 11, 34] Good [31, 44, 46, 60, 43, 38, 16, 64, 112, 46] Good [12, 30, 43, 109, 29, 43, 51, 22, 140, 21] Good [27, 81, 143, 36, 12, 12, 6, 63, 20, 100] Good [13, 16, 18, 96, 8, 65, 63, 55, 12, 154] Good [36, 49, 60, 62, 87, 53, 16, 32, 70, 35] Good [98, 17, 43, 61, 38, 57, 63, 77, 43, 3]``