Python利用带权重随机数解决抽奖和游戏爆装备问题

关于带权随机数
为了帮助理解，先来看三类随机问题的对比：
1.已有n条记录，从中选取m条记录，选取出来的记录前后顺序不管。
实现思路：按行遍历所有记录，约隔n/m条取一个数据即可
2.在1类情况下，还要求选取出来的m条记录是随机排序的
实现思路： 给n条记录，分别增加一列标记，值为随机选取的1至n之间的不重复数据。
3.区别于1,2类问题， 如果记录是有权重的，如何结合权重去随机选取。 比如A的权重为10， B的权重股为5， C的权重为1， 则随机选取4个时可能应该出现AABB。
第3类问题便是本文重点了。
实现思路： 以 A:10， B:5， C:1 三条记录上随机选取4条为例，（是否以权重排序这个无所谓）
    对于
    A 10
    B 5
    C 1
首先，将第n行的数值赋为第n行加第n-1行的，递归执行，如下：
    A 10
    B 15
    C 16
然后每次从[1,16]随机选取一个数，如果落在[1,10]之间，则选取A，如果落在(10,15]之间则选B，如果落在(16,16]之间则选取C， 图示如下，谁占的区间大（权重高），被选上的概率更大。

在抽奖和游戏爆装备中的运用
带权随机在游戏开发中重度使用,各种抽奖和爆装备等.
运营根据需要来配置各个物品出现的概率.
今天要说的这个带权随机算法思想很简单,就是"把所有物品根据其权重构成一个个区间,权重大的区间大.可以想象成一个饼图.  然后,扔骰子,看落在哪个区间,"
举个栗子,有个年终抽奖,物品是iphone/ipad/itouch.
主办方配置的权重是[('iphone', 10), ('ipad', 40), ('itouch', 50)].
用一行代码即可说明其思想,即random.choice(['iphone']*10 + ['ipad']*40 + ['itouch']*50).
下面,我们写成一个通用函数.

#coding=utf-8
import random
def weighted_random(items):
  total = sum(w for _,w in items)
  n = random.uniform(0, total)#在饼图扔骰子
  for x, w in items:#遍历找出骰子所在的区间
    if n<w:
      break
    n -= w
  return x 

print weighted_random([('iphone', 10), ('ipad', 40), ('itouch', 50)])

上面的代码够直观,不过细心的会发现,每次都会计算total,每次都会线性遍历区间进行减操作.其实我们可以先存起来,查表就行了.利用accumulate+bisect二分查找.
物品越多,二分查找提升的性能越明显.

#coding=utf-8
class WeightRandom:
  def __init__(self, items):
    weights = [w for _,w in items]
    self.goods = [x for x,_ in items]
    self.total = sum(weights)
    self.acc = list(self.accumulate(weights)) 

  def accumulate(self, weights):#累和.如accumulate([10,40,50])->[10,50,100]
    cur = 0
    for w in weights:
      cur = cur+w
      yield cur 

  def __call__(self):
    return self.goods[bisect.bisect_right(self.acc , random.uniform(0, self.total))] 

wr = WeightRandom([('iphone', 10), ('ipad', 40), ('itouch', 50)])
print wr()
赞 (0)

相关推荐

  • Python编程实现生成特定范围内不重复多个随机数的2种方法

    Python编程实现生成特定范围内不重复多个随机数的2种方法

    本文实例讲述了Python编程实现生成特定范围内不重复多个随机数的2种方法.分享给大家供大家参考,具体如下: 在近期进行的一个实验中,需要将数据按一定比例随机分割为两个部分.这一问题的核心其实就是产生不重复随机数的问题.首先想到的递归的方法,然后才发现Python中居然已经提供了此方法的函数,可以直接使用.具体代码如下: #生成某区间内不重复的N个随机数的方法 import random; #1.利用递归生成 resultList=[];#用于存放结果的List A=1; #最小随机数 B=10

  • python3生成随机数实例

    本文实例讲述了python3生成随机数的方法.分享给大家供大家参考.具体实现方法如下: 该实例是根据一本书上看到过一个随机数的小程序,经过自己改动,变为了一个猜数字的小游戏,现在在python3下重写了一遍. 这是一个控制台下的猜数程序,winxp+python3.2+eric5和IDLE测试通过,但直接用winxp的命令行运行有问题,原因还未知,慢慢找.ubuntu+python3.1测试通过. 具体实现代码如下: 复制代码 代码如下: # -*- coding: utf-8 -*- impo

  • Python生成随机数组的方法小结

    Python生成随机数组的方法小结

    本文实例讲述了Python生成随机数组的方法.分享给大家供大家参考,具体如下: 研究排序问题的时候常常需要生成随机数组来验证自己排序算法的正确性和性能,今天把Python生成随机数组的方法稍作总结,以备以后查看使用. 一.使用random模块生成随机数组 python的random模块中有一些生成随机数字的方法,例如random.randint, random.random, random.uniform, random.randrange,这些函数大同小异,均是在返回指定范围内的一个整数或浮点

  • python 生成不重复的随机数的代码

    复制代码 代码如下: import random print 'N must >K else error' n=int(raw_input("n=")) k=int(raw_input("k=")) result=[] x=range(n) for i in range(k): t=random.randint(i,n-1) temp=x[i] x[i]=x[t] x[t]=temp result.append(x[i]) print result raw_i

  • Python实现基于权重的随机数2种方法

    问题: 例如我们要选从不同省份选取一个号码,每个省份的权重不一样,直接选随机数肯定是不行的了,就需要一个模型来解决这个问题. 简化成下面的问题: 字典的key代表是省份,value代表的是权重,我们现在需要一个函数,每次基于权重选择一个省份出来 {"A":2, "B":2, "C":4, "D":10, "E": 20} 解决: 这是能想到和能看到的最多的版本,不知道还没有更高效好用的算法. #!/usr/

  • Python random模块（获取随机数）常用方法和使用例子

    random.randomrandom.random()用于生成一个0到1的随机符点数: 0 <= n < 1.0 random.uniformrandom.uniform(a, b),用于生成一个指定范围内的随机符点数,两个参数其中一个是上限,一个是下限.如果a > b,则生成的随机数n: a <= n <= b.如果 a <b, 则 b <= n <= a 复制代码 代码如下: print random.uniform(10, 20)print rand

  • Python中random模块生成随机数详解

    Python中的random模块用于生成随机数.下面介绍一下random模块中最常用的几个函数. random.random random.random()用于生成一个0到1的随机符点数: 0 <= n < 1.0 random.uniform random.uniform的函数原型为:random.uniform(a, b),用于生成一个指定范围内的随机符点数,两个参数其中一个是上限,一个是下限.如果a > b,则生成的随机数n: a <= n <= b.如果 a <

  • python生成指定长度的随机数密码

    复制代码 代码如下: #!/usr/bin/env python# -*- coding:utf-8 -*- #导入random和string模块import random, string def GenPassword(length):    #随机出数字的个数    numOfNum = random.randint(1,length-1)    numOfLetter = length - numOfNum    #选中numOfNum个数字    slcNum = [random.cho

  • Python生成随机数的方法

    如果你对在Python生成随机数与random模块中最常用的几个函数的关系与不懂之处,下面的文章就是对Python生成随机数与random模块中最常用的几个函数的关系,希望你会有所收获,以下就是这篇文章的介绍. random.random()用于生成 用于生成一个指定范围内的随机符点数,两个参数其中一个是上限,一个是下限.如果a > b,则生成随机数 n: a <= n <= b.如果 a <b, 则 b <= n <= a. print random.uniform(

  • Python随机数用法实例详解【基于random模块】

    本文实例讲述了Python随机数用法.分享给大家供大家参考,具体如下: 1. random.seed(int) 给随机数对象一个种子值,用于产生随机序列. 对于同一个种子值的输入,之后产生的随机数序列也一样. 通常是把时间秒数等变化值作为种子值,达到每次运行产生的随机系列都不一样 seed() 省略参数,意味着使用当前系统时间生成随机数 random.seed(10) print random.random() #0.57140259469 random.seed(10) print rando

  • Python2随机数列生成器简单实例

    本文实例讲述了Python2随机数列生成器.分享给大家供大家参考,具体如下: #filename:randNumber.py import random while True: try: row=int(raw_input('Enter the rows:')) cols=int(raw_input('then Enter the cols:')) minNum=int(raw_input('then Enter the minNumber:')) maxNum=int(raw_input('t

随机推荐