一个红包随机分配算法


#算法#


2016-04-23

本文简单的讨论一下随机分配红包的算法实现。若有雷同,纯属巧合。

如何生成指定范围内的随机整数

Python的random库提供了randint函数用于得到整数a和整数b之间的一个随机的整数(包括a和b,其中a<=b)。

import random
a=1
b=100
print random.randint(a,b)

randint函数可以基于random函数实现。random函数可以随机生成[0.0, 1.0)之间的一个小数,注意是左闭右开的区间。

下面的my_randint01函数可以得到一个左闭右开区间中的随机整数:

import random

def my_randint01(left, right):
    if left>=right:
        raise Exception('...')
    rand_number = random.random()
    result = left+rand_number*(right-left)
    return int(result)

if __name__ == '__main__':
    for _ in range(10):
        print my_randint01(2, 6)

下面的my_randint02函数可以得到一个左闭右闭区间中的随机整数:

import random

def my_randint02(left, right):
    if left>right:
        raise Exception('...')
    rand_number = random.random()
    result = left+rand_number*(right-left+1)  # 此处略有改动
    return int(result)

if __name__ == '__main__':
    for _ in range(10):
        print my_randint01(2, 6)

红包分配要考虑的情况

用户看到的是红包单位是,不过RMB的最小单位是分,将金额从转换为也许更容易处理。

用户拿到的红包转换为时,必须是整数。

4分钱发给4个朋友,每个人都应该得到1分的红包。

4分钱不能发给5个朋友。

100分钱发给4个朋友要体现出随机性。

来,发红包

100分钱发给4个人,可以先得到4个大于0的在一定范围内的随机整数。每个人对应一个随机整数,通过这个随机整数可以得到他收到的红包大小在100分钱中的比例,然后按照比例分配。在此基础上还需要考虑下面的细节问题:

1、 涉及到浮点数的乘除法,如果一个人最终得到了0.2分钱,转转成整数该是0分钱还是1分钱? 解决办法是先给每个人分配1分钱。

2、 涉及到浮点数的乘除法,最后分配的红包取整后的和不一定等于100。解决方法是:每个人的红包向下取整,第4个人直接把剩下的拿到手即可。

3、 按照上面的思路,5分钱分给4个人,第四个人稳拿2分钱。解决方法是:红包分配好后再随机打乱。

最终算法如下:

#coding: utf-8
import random

def red_envelope(cents, people_number):

    if (not isinstance(cents, int)) or (not isinstance(people_number, int)):
        raise Exception('invalid type!')

    if cents < people_number:
        raise Exception('too many people!')

    if cents <= 0 or people_number <= 0:
        raise Exception('Are you kidding me ?')

    if cents == people_number:
        return [1] * people_number

    if people_number == 1:
        return [cents]

    fix_result = [1] * people_number
    cents = cents - 1*people_number
    balance = cents
    rand_result = []
    rand_numbers = []
    for _ in range(people_number):
        rand_numbers.append(random.randint(10,100))
    rand_sum = float(sum(rand_numbers))

    for idx in range(people_number):
        if idx == people_number - 1:
            rand_result.append(balance)
        else:
            scale = rand_numbers[idx] / rand_sum
            your_cents = int(cents*scale)
            rand_result.append(your_cents)
            balance = balance - your_cents

    result = []
    for fix, rand in zip(fix_result, rand_result):
        result.append(fix+rand)

    random.shuffle(result)  # shuffle the result

    return result


# test
if __name__ == '__main__':
    result = red_envelope(100, 10)
    print result, sum(result)

某次输出结果:

[15, 10, 11, 10, 3, 7, 14, 3, 20, 7] 100

( 本文完 )