2

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

假设我有一个清单：

{1,3,6}

我想从该列表中获取一个随机项目，但是，我希望它与项目的值直接（概率）加权。因此，如果您运行它 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
}

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

4

4 回答 4

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>>其中每个元组都是一个项目/重量对。

于 2013-07-28T19:36:38.950 回答
2

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

{1,3,3,3,6,6,6,6,6,6}
于 2013-07-28T19:39:57.027 回答
1

再试一次:)

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];
}

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

于 2013-07-28T19:49:28.553 回答
0

这是俄罗斯轮盘赌的通用算法。

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);
于 2013-07-28T19:38:35.147 回答