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

Question

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

说我有一个清单:

{1,3,6}

我想从该列表中获取一个随机项目,但是我希望它能够直接(概率方面)与项目的值进行加权.因此,如果您运行100,000次,1则将选择大约10,000次,3将选择大约30,000次,并且选择660,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>>其中每个元组是项目/权重对.