如何按概率选择项目？

Question

我有一个项目清单.这些项目中的每一项都有自己的概率.

任何人都可以提出一种基于其概率选择项目的算法吗？

Answer 1

1. 生成均匀分布的随机数.
2. 遍历您的列表,直到被访问元素的累积概率大于随机数

示例代码:

double p = Math.random();
double cumulativeProbability = 0.0;
for (Item item : items) {
    cumulativeProbability += item.probability();
    if (p <= cumulativeProbability) {
        return item;
    }
}

Answer 2

因此,每个项目都会存储一个标记其相对概率的数字,例如,如果您有3个项目,那么选择其中两个项目的可能性应该是其他两个项目的两倍,那么您的列表将具有:

 [{A,1},{B,1},{C,2}]

然后将列表的数字相加(即在我们的例子中为4).现在生成一个随机数并选择该索引.int index = rand.nextInt(4); 返回数字,使索引处于正确的范围内.

Java代码:

class Item {
    int relativeProb;
    String name;

    //Getters Setters and Constructor
}

...

class RandomSelector {
    List<Item> items = new List();
    Random rand = new Random();
    int totalSum = 0;

    RandomSelector() {
        for(Item item : items) {
            totalSum = totalSum + item.relativeProb;
        }
    }

    public Item getRandom() {

        int index = rand.nextInt(totalSum);
        int sum = 0;
        int i=0;
        while(sum < index ) {
             sum = sum + items.get(i++).relativeProb;
        }
        return items.get(Math.max(0,i-1));
    }
}

Answer 3

假装我们有以下列表

Item A 25%
Item B 15%
Item C 35%
Item D 5%
Item E 20%

让我们假装所有概率都是整数,并为每个项目分配一个"范围",计算如下.

Start - Sum of probability of all items before
End - Start + own probability

新数字如下

Item A 0 to 25
Item B 26 to 40
Item C 41 to 75
Item D 76 to 80
Item E 81 to 100

现在选择一个从0到100的随机数.让我们说你选择32. 32落在项目B的范围内.

MJ

Answer 4

您可以尝试轮盘赌轮选择.

首先,添加所有概率,然后通过将每个概率除以总和来缩放1的所有概率.假设概率是A(0.4), B(0.3), C(0.25) and D(0.05).然后,您可以生成[0,1]范围内的随机浮点数.现在你可以这样决定:

random number between 0.00 and 0.40 -> pick A
              between 0.40 and 0.70 -> pick B
              between 0.70 and 0.95 -> pick C
              between 0.95 and 1.00 -> pick D

您也可以使用随机整数 - 比如生成0到99之间的随机整数(包括),然后就可以像上面那样做出决定.

Answer 5

Ushman,Brent和@ kaushaya的答案中描述的算法在Apache commons-math库中实现.

看看EnumeratedDistribution类(后面的groovy代码):

def probabilities = [
   new Pair<String, Double>("one", 25),
   new Pair<String, Double>("two", 30),
   new Pair<String, Double>("three", 45)]
def distribution = new EnumeratedDistribution<String>(probabilities)
println distribution.sample() // here you get one of your values

请注意,概率之和不需要等于1或100 - 它将自动归一化.

Answer 6

我的方法非常简单.生成一个随机数.现在,由于您的项目的概率已知,只需遍历排序的概率列表并选择概率小于随机生成的数字的项目.

有关详细信息,请在此处阅读我的答案.

Answer 7

一种缓慢但简单的方法是让每个成员根据其概率选择一个随机数，然后选择具有最高价值的一个。

比喻：

想象一下，需要选择3个人中的1个人，但是他们有不同的概率。你给他们死去的面孔数量不同。第一人称骰子有4个面孔，第二人称骰子有6个面孔，第三人称骰子有8个面孔。

可以说我们有以下列表：

[{A,50},{B,100},{C,200}]

伪代码：

 A.value = random(0 to 50);
 B.value = random(0 to 100);
 C.value = random (0 to 200);

我们选择价值最高的那个。

上面的这种方法不能准确地映射概率。例如，100不会是50的两倍。但是，我们可以通过稍微调整一下方法来做到这一点。

方法2

可以选择从前一个变量的上限到当前变量的加法，而不是从0到权重之间选择一个数字。

[{A,50},{B,100},{C,200}]

伪代码：

 A.lowLimit= 0; A.topLimit=50;
 B.lowLimit= A.topLimit+1; B.topLimit= B.lowLimit+100
 C.lowLimit= B.topLimit+1; C.topLimit= C.lowLimit+200 

结果限制

A.limits = 0,50
B.limits = 51,151
C.limits = 152,352

然后我们选择一个从0到352的随机数，并将其与每个变量的限制进行比较，以查看该随机数是否在其限制内。

我相信这种调整具有更好的性能，因为只有1个随机代。

在其他答案中也有类似的方法，但是此方法不需要总数为100或1.00。

Answer 8

一种占用空间的方法是克隆每个项目的次数是其概率的倍。选择将在 O(1) 内完成。

例如

//input
[{A,1},{B,1},{C,3}]

// transform into
[{A,1},{B,1},{C,1},{C,1},{C,1}]

然后只需从这个转换后的列表中随机选择任何项目即可。