c# - 从列表中选择随机项目的快速方法 - 基于项目值的不同概率？

Question

(如果不编写一个适当大小的辅助方法，这可能是不可能的，但无论如何，我想弄清楚)

假设我有一个列表:

{1,3,6}

我想从该列表中随机获取一个项目，但是，我希望它直接(按概率)根据项目的值(value)进行加权。因此，如果您运行它 100,000 次，1 将被选择约 10,000 次，3 将被选择约 30,000 次，而 6 , 60,000 次。

我可能只是通过创建这样的范围来编写一个辅助方法:

{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
}

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

Answer 1

您已经掌握了基本思路 - 对权重求和(碰巧 与您此处的值相同)并取该范围内的随机数 - 尽管我会使用 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>> 的参数其中每个元组是一个项目/权重对。