是否有一个过程可以使用求和树根据其反向优先级从数组中进行采样？

Question

我正在尝试根据数组的优先级和反转优先级从数组中进行采样。通过使用和树结构，可以直接进行优先采样。但是，我不知道如何对反向优先级进行采样。

假设我们有一个数组 [1,2,3,4]，我在每次迭代时采样一个元素。如果我执行 N 次迭代（并且 N 是一个非常大的数字），我期望通过使用优先采样获得第一个元素 N/10 次，第二个元素 2N/10 次等。在反向优先采样设置中，我期望获得第一个元素12N/25次，第二个元素6N/25次，第三个元素4N/25次，第四个元素3N/25次。我想不出一种算法来执行反向优先采样。

为了清楚起见，本文解释了使用和树的优先采样算法：https://www.fcodelabs.com/2019/03/18/Sum-Tree-Introduction/

Answer 1

Python 中的一行：

import random    # choices

population = ['A', 'B', 'C', 'D']
priorities = [1,2,3,4]
N = 100

random.choices(population, weights=[1/p for p in priorities], k=N)

或者，如果您想将精确权重计算为整数而不是浮点数：

import random    # choices
import math      # prod

population = ['A', 'B', 'C', 'D']
priorities = [1,2,3,4]
N = 100

product = math.lcm(priorities)     # python<=3.8 doesn't have lcm, but can use either  math.prod(priorities)  or  math.prod(priorities)//math.gcd(priorities)
weights = [product // p for p in priorities]  # integers proportional to 1/p

random.choices(population, weights=weights, k=N)