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

实现基于权重的随机数，在Python中有至少两种常见的方法：轮盘法和分段函数法。下面将分别进行详细介绍和代码实现。

方法1：轮盘法

简介

轮盘法是一种基于概率的产生随机数的算法。可以根据给定元素的权重值，计算出每个元素上的权重区间，再将这些区间按顺序排列，在一个[0,1)的随机数范围内生成一个随机数，最后根据这个随机数所在的区间，确定选中的元素。

实现步骤

1. 计算每个元素的权重值。
2. 根据权重值计算出每个元素对应的权重区间。
3. 将各个元素的权重区间从小到大排列。
4. 生成一个随机数R，计算其在权重区间中的位置。
5. 找出包含这个位置的区间，得到所选元素。

示例1

假设有以下三个元素及其权重值：

elements = ['A', 'B', 'C']
weights = [0.2, 0.3, 0.5]

我们可以计算出各个元素对应的权重区间：

intervals = [sum(weights[:i+1]) for i in range(len(weights))]
# 等价于 [0.2, 0.5, 1.0]

接下来，我们将这些区间从小到大排列：

sorted_intervals = sorted(intervals)
# [0.2, 0.5, 1.0]

生成一个随机数R，计算其在权重区间中的位置：

import random

R = random.uniform(0, 1)
pos = len(sorted_intervals) - 1  # 默认选B
for i, val in enumerate(sorted_intervals):
    if R < val:
        pos = i
        break

最后，我们可以根据pos确定选中的元素：

selected_element = elements[pos]
print(selected_element)
# 如果生成的R在[0, 0.2)范围内，选中元素为A，如果在[0.2, 0.5)范围内，选中元素为B，如果在[0.5, 1.0)范围内，选中元素为C。

示例2

如果有一组元素和权重值如下：

elements = ['A', 'B', 'C', 'D', 'E']
weights = [1, 2, 3, 4, 5]

我们可以使用类似的方式计算出元素对应的权重区间：

intervals = [sum(weights[:i+1]) / sum(weights) for i in range(len(weights))]
sorted_intervals = sorted(intervals)

然后模拟生成1000个随机数，并统计每个元素被选择的次数：

from collections import defaultdict

result = defaultdict(int)
for i in range(1000):
    R = random.uniform(0, 1)
    pos = len(sorted_intervals) - 1
    for i, val in enumerate(sorted_intervals):
        if R < val:
            pos = i
            break
    selected_element = elements[pos]
    result[selected_element] += 1

for key, val in result.items():
    print("{}: {}".format(key, val))

输出的结果类似于：

A: 55
B: 114
C: 171
D: 215
E: 445

可以看到，元素E被选择的次数最多，符合其权重值较大的特点。

方法2：分段函数法

简介

分段函数法是另一种实现基于权重的随机数的方法。这个方法将元素和权重值看做一个有序对，根据所有有序对的权重值，计算出一个权重的分段函数，再在一个[0,1)的随机数范围内生成随机数，最后根据随机数所在的区间，确定选中的元素。

实现步骤

1. 将元素和权重值组成有序对。
2. 根据所有有序对的权重值计算出一个权重的分段函数。
3. 在[0,1)范围内生成一个随机数R。
4. 根据R在分段函数中的位置，确定所选元素。

示例1

假设有以下三个元素及其权重值：

pairs = [('A', 0.2), ('B', 0.3), ('C', 0.5)]

我们可以计算出所有权重值的和，以此计算出每一个元素的权重区间范围，得到一个分段函数：

sum_weight = sum([p[1] for p in pairs])
interval_list = []
interval_sum = 0
for pair in pairs:
    interval_sum += pair[1] / sum_weight
    interval_list.append((pair[0], interval_sum))

然后，我们可以生成一个随机数R，并根据R在分段函数中的位置，确定选择的元素：

R = random.uniform(0, 1)
selected_element = None
for interval in interval_list:
    if R < interval[1]:
        selected_element = interval[0]
        break

最后，我们可以输出所选的元素：

print(selected_element)

如果生成的R在[0, 0.2)范围内，选中元素为A，如果在[0.2, 0.5)范围内，选中元素为B，如果在[0.5, 1.0)范围内，选中元素为C。

示例2

如果有一组元素和权重值如下：

pairs = [('A', 1), ('B', 2), ('C', 3), ('D', 4), ('E', 5)]

我们可以使用类似的方式计算出分段函数：

sum_weight = sum([p[1] for p in pairs])
interval_list = []
interval_sum = 0
for pair in pairs:
    interval_sum += pair[1] / sum_weight
    interval_list.append((pair[0], interval_sum))

然后模拟生成1000个随机数，并统计每个元素被选择的次数：

result = defaultdict(int)
for i in range(1000):
    R = random.uniform(0, 1)
    selected_element = None
    for interval in interval_list:
        if R < interval[1]:
            selected_element = interval[0]
            break
    result[selected_element] += 1

for key, val in result.items():
    print("{}: {}".format(key, val))

输出的结果类似于：

A: 48
B: 121
C: 300
D: 273
E: 258

可以看到，元素C被选择的次数最多，符合其权重值较大的特点。