algorithm - 动态偏向随机选择算法

Question

我正在寻求实现一种从列表中随机挑选项目的算法，尽管是以一种有偏见的方式。假设我对该列表中的每个元素都有一个 priority 值。我希望具有更高优先级的元素在选择中更频繁地出现。

另一件事是这些元素的优先级会改变。如果有人特别选择一个元素而不是让该元素来自随机选择，则该元素的优先级应该增加一定的因素。

恐怕我不太确定如何用数学来表达我的问题。另外，我也不知道从哪里开始。我找到一篇文章 here它处理第一部分但不处理动态增加元素的优先级。

我想到的一种方法是元素的优先级越高，我们复制它的次数就越多。然而，这在计算机代码中是非常不可行的

我还在 math.stackexchange 上发布了这个问题，希望获得一些数学见解。

注意:需要说明的是，我并不是在寻找任何类型的实现。我只是在寻找一个明确的方向/一些见解，这样我就可以继续编写我自己的算法。

Answer 1

我现在能想到的一种可能的方法是，

假设有两个数组，priority[k]和values[k]

priority[]={2,1,5,7}
values[]={"apple","banana","oranges","lollipop"}

以有偏的方式获取随机值:
1.设优先级数组的总和为S，本例中S=15。
2.有优先数组的累积数组，

`cumulative[]= {2,3,8,15}

3。现在生成一个随机数 r <=S。假设是7
4. 7 <8，累积数组中的第三个元素。所以你返回“橙色” 如果 r=3，返回“banana”，如果 r=10，返回“lollipop”。

如果有人特别选择了一个元素，只需将该元素的优先级值增加 k 倍即可。

假设k=2，有人选择橘子，新的数组是

priority[]={2,1,7,7}
values[]={"apple","banana","oranges","lollipop"}
cumulative={2,3,10,17}

使用与上述相同的算法，您将获得所需的结果。