根据项目值从中选择具有不同概率的随机项目的快速方法

本文关键字：项目 概率 随机 方法 选择 | 更新日期: 2023-09-27 18:25:11

假设我有一个列表：

{1,3,6}

我想从这个列表中得到一个随机项目，但是，我希望它直接（按概率）与项目的值加权。因此，如果你运行它100000次，1将被选择大约10000次，3将被选择约30000次，而6将被选择60000次。

我可以通过创建这样的范围来编写一个辅助方法：

{1,3,6}
Generate random number between 1(inclusive) and 11(exclusive) (sum of list)
if (number == 0)
{
    //1
}
else if (number > 0 && number < 4)
{
    //3
}
else
{
    //6
}

虽然这个特定的例子相当简单，但我经常处理大列表，它们总是不同的，所以会有点复杂。虽然我可以做到，但我很好奇是否有更简单的方法。

根据项目值从中选择具有不同概率的随机项目的快速方法

您已经有了基本的想法-求和权重（与此处的值相同），并在该范围内取一个随机数-尽管我会使用0作为下界，使用和作为唯一上界。然后，你只需要浏览列表，找出哪个值对应于…从列表的开头开始，并不断检查随机数是否小于当前项目的权重：如果是，那就是所选项目。如果不是，从随机数中减去权重，然后继续。

无可否认，这是一个O（N）算法。如果你需要多次从同一列表中提取一个随机数，你可以建立一个累积权重列表，然后进行二进制搜索，找出哪个索引对应哪个随机数。。。但我会先坚持相对简单的方法。

我还没有测试过，但它可能是这样的：

// Note: this will iterate over the sequence twice. It's expected not to change
// between iterations!
// The Random parameter is so that you can use a single instance multiple times.
// See http://csharpindepth.com/Articles/Chapter12/Random.aspx
int PickRandomWeightedElement(IEnumerable<int> sequence, Random random)
{
    int totalWeight = sequence.Sum();
    int weightedPick = random.Next(totalWeight);
    foreach (var item in sequence)
    {
        if (weightedPick < item)
        {
            return item;
        }
        weightedPick -= item;
    }
    throw new InvalidOperationException("List must have changed...");
}

如果需要将项与权重分离，可以使用两个参数（一个用于权重，一个用于项）或IEnumerable<Tuple<T, int>>类型的参数，其中每个元组都是项/权重对。

我会让统计和概率通过多次添加相同的元素来运行。那样你就会使统计数据失真。随着时间的推移，您将拥有您正在寻找的分发

{1,3,3,3,6,6,6,6,6,6}

还有一次尝试：）

public static object GetRandom(this IList list, List<int> weights){
    var sum = weights.Sum();
    var r = new Random().Next(1,sum);
    var w = 0;
    var i = -1;
    while(w <= r){
        i++;
        w+=weights[i];
    }
    return list[i];
}

如果你想优化speen和随机性，你可以预先计算权重总和并重用Random实例，并将它们作为参数传递。或者甚至从权重列表中格式化累积和列表，以消除循环中的算术运算。

这里有一个俄罗斯轮盘赌的通用算法。

private static Random random = new Random();
public static T GetRandomItem<T>(Dictionary<T, int> items)
{
    int sum = items.Values.Sum();
    int cumulatedProbability = random.Next(sum);
    foreach(var item in items)
        if((cumulatedProbability -= item.Value) < 0)
            return item.Key;
    throw new InvalidOperationException();
}

使用它：

Dictionary<string, int> items = new Dictionary<string, int> { { "Item 1", 10000 }, { "Item 2", 30000 }, { "Item 3", 60000 } };
var randomItem = GetRandomItem(items);
相关文章：