如何根据概率选择一个项目？

我有一个项目列表。每个项目都有自己的概率。

有人能提出一个算法来根据概率选择一个项目吗？

68462 次浏览
小开
最佳答案

因此，对于每个商品存储一个数字来标记它的相对概率，例如，如果你有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));
}
}
小开

假装我们有以下列表

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

小开

你可以试试 轮盘赌选择。

首先，将所有的概率相加，然后将所有的概率按1的尺度进行缩放，将每个概率除以和。假设缩放概率是 A(0.4), B(0.3), C(0.25) and D(0.05)。然后您可以在范围 [0, 1)内生成一个随机的浮点数。现在你可以这样决定:

random number in [0.00, 0.40) -> pick A
in [0.40, 0.70) -> pick B
in [0.70, 0.95) -> pick C
in [0.95, 1.00) -> pick D

你也可以用随机整数来做这件事——比如你生成一个0到99之间的随机整数(包括0到99) ，然后你可以像上面那样做决定。

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

示例代码:

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

布伦特的回答 是好的，但是它没有考虑到在 p = 0的情况下错误选择概率为0的项目的可能性。这很容易通过检查概率来处理(或者可能一开始就没有添加条目) :

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

我的方法很简单。生成一个随机数。现在，既然已经知道了项目的概率，那么只需要遍历已排序的概率列表，并选择概率小于随机生成的数字的项目。

更多细节，请阅读我的答案 给你。

小开

在 阿帕奇公共数学库中实现了 Ushman 的、 Brent 的和@kushaya 答案中描述的算法。

看一下 枚举分布类(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-它将被自动规范化。

小开

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

类比:

想象一下，三个人中的一个需要被选中，但是他们有不同的概率。你给他们不同数量的面孔死亡。第一个人的骰子有四个面，第二个人的骰子有六个面，第三个人的骰子有八个面。他们掷骰子，数字最大的人赢。

假设我们有以下列表:

[{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。

小开

你可以用茱莉亚密码:

function selrnd(a::Vector{Int})
c = a[:]
sumc = c[1]
for i=2:length(c)
sumc += c[i]
c[i] += c[i-1]
end
r = rand()*sumc
for i=1:length(c)
if r <= c[i]
return i
end
end
end

此函数有效地返回项的索引。

小开

如果不介意在代码中添加第三方依赖项，可以使用 概率()方法。

例如:

String s = mockNeat.probabilites(String.class)
.add(0.1, "A") // 10% chance to pick A
.add(0.2, "B") // 20% chance to pick B
.add(0.5, "C") // 50% chance to pick C
.add(0.2, "D") // 20% chance to pick D
.val();

免责声明: 我是图书馆的作者，所以当我推荐它的时候，我可能会有偏见。

小开

所有提到的解决方案都是线性的。下面只有对数的努力，也处理非标准化的概率。我建议使用 TreeMap 而不是 List:

    import java.util.*;
import java.util.stream.IntStream;


public class ProbabilityMap<T> extends TreeMap<Double,T>{
private static final long serialVersionUID = 1L;
public static Random random = new Random();
public double sumOfProbabilities;
public Map.Entry<Double,T> next() {
return ceilingEntry(random.nextDouble()*sumOfProbabilities);
}
@Override public T put(Double key, T value) {
return super.put(sumOfProbabilities+=key, value);
}
public static void main(String[] args) {
ProbabilityMap<Integer> map = new ProbabilityMap<>();
map.put(0.1,1);  map.put(0.3,3);    map.put(0.2,2);
IntStream.range(0, 10).forEach(i->System.out.println(map.next()));
}
}
小开

将 https://stackoverflow.com/a/37228927/11257746中的代码改编成一个通用的扩展方法。这将允许您从具有 < TKey，int > 结构的 Dictionary 中获得一个加权随机值，其中 int 是一个加权值。

值为50的键被选中的可能性是值为5的键的10倍。

使用 LINQ 的 C # 代码:

/// <summary>
/// Get a random key out of a dictionary which has integer values treated as weights.
/// A key in the dictionary with a weight of 50 is 10 times more likely to be chosen than an element with the weight of 5.
///
/// Example usage to get 1 item:
/// Dictionary<MyType, int> myTypes;
/// MyType chosenType = myTypes.GetWeightedRandomKey<MyType, int>().First();
///
/// Adapted into a general extention method from https://stackoverflow.com/a/37228927/11257746
/// </summary>
public static IEnumerable<TKey> GetWeightedRandomKey<TKey, TValue>(this Dictionary<TKey, int> dictionaryWithWeights)
{
int totalWeights = 0;
foreach (KeyValuePair<TKey, int> pair in dictionaryWithWeights)
{
totalWeights += pair.Value;
}


System.Random random = new System.Random();
while (true)
{
int randomWeight = random.Next(0, totalWeights);
foreach (KeyValuePair<TKey, int> pair in dictionaryWithWeights)
{
int weight = pair.Value;


if (randomWeight - weight > 0)
randomWeight -= weight;
else
{
yield return pair.Key;
break;
}
}
}
}

示例用法:

public enum MyType { Thing1, Thing2, Thing3 }
public Dictionary<MyType, int> MyWeightedDictionary = new Dictionary<MyType, int>();


public void MyVoid()
{
MyWeightedDictionary.Add(MyType.Thing1, 50);
MyWeightedDictionary.Add(MyType.Thing2, 25);
MyWeightedDictionary.Add(MyType.Thing3, 5);
    

// Get a single random key
MyType myChosenType = MyWeightedDictionary.GetWeightedRandomKey<MyType, int>().First();
    

// Get 20 random keys
List<MyType> myChosenTypes = MyWeightedDictionary.GetWeightedRandomKey<MyType, int>().Take(20).ToList();
}
小开

一个耗费空间的方法是克隆每个项目的数量乘以它的概率。选择将在 O (1)中完成。

比如说

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


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

然后简单地从这个转换后的列表中随机挑选任何项目。


提交答案