基于百分比加权的选择

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

Knuth提到了沃克的别名方法。查找这个方法时，我发现了两个链接：http://code.activestate.com/recipes/576564-walkers-alias-method-for-random-objects-with-diffe/ 和 http://prxq.wordpress.com/2006/04/17/the-alias-method/。这个方法可以在生成每个数字时以恒定的时间给出准确的概率，而设置这个方法需要线性的时间（有趣的是，如果你使用Knuth描述的确切方法，设置需要n log n的时间，因为它需要进行一个准备排序，而这个排序是可以避免的）。

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个项目的列表，但它们的行为是完全一样的。如果你觉得在特定的应用场景中这个内存占用问题很重要，可以考虑把概率列表中的所有计数都除以它们的最大公约数。

除了内存占用的问题，这种方法应该是最快的解决方案——每次输出结果只需要生成一个随机数，而且从这个随机数中查找结果的速度也是最快的，不需要进行比较等操作。如果你的概率值非常复杂（比如需要匹配很多小数位的浮点数），那么可能需要考虑其他方法；-）

Answer 3

这里有一个完整的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());