Python uses weighted random numbers to solve lottery and game equipment explosions

About weighted random numbers

To help understand, let’s first look at the comparison of three types of random problems:
1. There are n records, select from them m records, the order of the selected records does not matter.
Implementation idea: traverse all records by row, and take one piece of data every n/m records
2. In type 1 situation, it is also required that the selected m records be randomly sorted
Implementation Idea: Add a column of markers to each of n records, and the values ​​are randomly selected non-duplicate data between 1 and n.
3. Different from type 1 and 2 problems, if the records have weights, how to randomly select them based on the weights. For example, the weight of A is 10, the weight of B is 5, and the weight of C is 1, then AABB should probably appear when 4 are randomly selected.
The third type of problem is the focus of this article.
Implementation idea: Take 4 randomly selected records from A:10, B:5, C:1 as an example (it doesn’t matter whether they are sorted by weight)
For
A 10
B 5
C 1
First, assign the value of the n-th row to the n-th row plus the n-1th row, and execute it recursively, as follows:
A 10
B 15
C 16
Then randomly select a number from [1,16] each time. If it falls between [1,10], select A. If it falls between (10,15], select B. If it falls between (16) ,16], choose C. The diagram is as follows. Whoever occupies a larger interval (higher weight) has a greater probability of being selected.

##Use in lottery and game explosive equipment
Righted random is heavily used in game development, various lottery draws and explosive equipment, etc.Operation based on needs To configure the probability of each item appearing.
The idea of ​​the weighted random algorithm we are going to talk about today is very simple, that is, "all items are formed into intervals according to their weights, and the intervals with larger weights are larger. It can be imagined as a pie chart." Then, throw the dice to see which range it falls in, "
For example, there is a year-end lottery, and the item is iphone/ipad/itouch.
The weight configured by the organizer is [('iphone', 10), ('ipad', 40), ('itouch', 50)].
The idea can be explained with one line of code, that is, random.choice(['iphone']*10 + ['ipad']*40 + ['itouch']*50).
Below, we write it as a general function.

#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([(&#39;iphone&#39;, 10), (&#39;ipad&#39;, 40), (&#39;itouch&#39;, 50)])

The above code is intuitive enough, but be careful You will find that total will be calculated every time, and each time it will linearly traverse the interval for subtraction. In fact, we can save it first and look up the table. Use accumulate+bisect binary search.

The more items there are, the better the binary search will be. The more obvious the performance.

##

#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()

For more articles related to Python’s use of weighted random numbers to solve lottery and game equipment explosions, please pay attention to the PHP Chinese website ##!

#