基于百分比加权的选择

Question

我有一组值,每个值都有一个相关的百分比:

a:70%几率
b:20%几率
c:10%几率

我想根据给定的百分比机会选择一个值(a,b,c).

我该如何处理？

到目前为止我的尝试看起来像这样:

r = random.random()
if r <= .7:
    return a
elif r <= .9:
    return b
else: 
    return c

我很难想出一个算法来处理这个问题.我该如何处理这个问题,以便它可以处理更大的值集,而不需要将if-else流链接在一起.

(伪代码中的任何解释或答案都很好.一个python或C#实现会特别有用)

Answer 1

这是C#中的完整解决方案:

public class ProportionValue<T>
{
    public double Proportion { get; set; }
    public T Value { get; set; }
}

public static class ProportionValue
{
    public static ProportionValue<T> Create<T>(double proportion, T value)
    {
        return new ProportionValue<T> { Proportion = proportion, Value = value };
    }

    static Random random = new Random();
    public static T ChooseByRandom<T>(
        this IEnumerable<ProportionValue<T>> collection)
    {
        var rnd = random.NextDouble();
        foreach (var item in collection)
        {
            if (rnd < item.Proportion)
                return item.Value;
            rnd -= item.Proportion;
        }
        throw new InvalidOperationException(
            "The proportions in the collection do not add up to 1.");
    }
}

用法:

var list = new[] {
    ProportionValue.Create(0.7, "a"),
    ProportionValue.Create(0.2, "b"),
    ProportionValue.Create(0.1, "c")
};

// Outputs "a" with probability 0.7, etc.
Console.WriteLine(list.ChooseByRandom());

Answer 2

对于Python:

>>> import random
>>> dst = 70, 20, 10
>>> vls = 'a', 'b', 'c'
>>> picks = [v for v, d in zip(vls, dst) for _ in range(d)]
>>> for _ in range(12): print random.choice(picks),
... 
a c c b a a a a a a a a
>>> for _ in range(12): print random.choice(picks),
... 
a c a c a b b b a a a a
>>> for _ in range(12): print random.choice(picks),
... 
a a a a c c a c a a c a
>>> 

一般想法:列出每个项目重复多次的列表,与其应有的概率成比例; 用于random.choice随机选择一个(统一),这将符合您所需的概率分布.如果你的概率以特殊的方式表达,可能会有点浪费内存(例如,70, 20, 10制作100个项目列表,其中7, 2, 1只列出10个具有完全相同行为的项目),但是你可以将概率中的所有计数除以如果您认为在您的特定应用场景中可能会有大问题,请列出它们最常见的因素.

除了内存消耗问题,这应该是最快的解决方案 - 每个所需的输出结果只生成一个随机数,并且从该随机数中找到最快的查找,没有比较&c.如果您可能的概率非常奇怪(例如,需要与许多有效数字相匹配的浮点数),其他方法可能更可取;-).

Answer 3

Knuth references Walker's method of aliases. Searching on this, I find http://code.activestate.com/recipes/576564-walkers-alias-method-for-random-objects-with-diffe/ and http://prxq.wordpress.com/2006/04/17/the-alias-method/. This gives the exact probabilities required in constant time per number generated with linear time for setup (curiously, n log n time for setup if you use exactly the method Knuth describes, which does a preparatory sort you can avoid).

Answer 4

取列表并找出累计总重量:70,70 + 20,70 + 20 + 10.选择一个大于或等于零且小于总数的随机数.迭代项目并返回权重的累积总和大于此随机数的第一个值:

def select( values ):
    variate = random.random() * sum( values.values() )
    cumulative = 0.0
    for item, weight in values.items():
        cumulative += weight
        if variate < cumulative:
            return item
    return item # Shouldn't get here, but just in case of rounding...

print select( { "a": 70, "b": 20, "c": 10 } )

实施的这个解决方案也应该能够处理加权到任何数字的分数权重和权重,只要它们都是非负数.