我有一组值，每个值都有一个对应的百分比：
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#实现的解释都可以。）
以下是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());
public static T ChooseByRandom<T>(this System.Collections.Generic.IEnumerable<ProportionValue<T>> collection)。 - Jonny对于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个元素的列表），那么可能会浪费一些内存，但是如果您认为这在特定应用场景下很重要，可以将概率列表中的所有计数除以它们的最大公因数。
除了内存消耗问题外，这应该是最快的解决方案-每个所需输出结果只需要生成一个随机数，并且从该随机数中进行最快可能的查找，不需要比较等操作。如果您的可能概率非常奇怪（例如，需要将浮点数与许多有效数字匹配），则可能会优先考虑其他方法;-)。
picks生成器，它也非常容易理解。但是，我觉得有点难以推荐一个局限的解决方案，尤其当一个更通用的方案几乎同样简单时。 - Mark RansomKnuth提到了Walker的别名方法。在搜索中，我找到了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时间进行准备排序，但您可以避免这一步骤）。
将权重列表累加得到：70、70+20、70+20+10。随机选择一个大于或等于0且小于总和的数字。遍历项目并返回第一个值，其中权重的累积和大于此随机数：
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 } )
这个解决方案实现后，应该能够处理分数权重和加起来等于任何非负数的权重。
def weighted_choice(probabilities):
random_position = random.random() * sum(probabilities)
current_position = 0.0
for i, p in enumerate(probabilities):
current_position += p
if random_position < current_position:
return i
return None
random.random总是返回小于 1.0的值，所以最终的return语句永远不会被执行。sum(probabilities) 就不是必要的了。这段代码也能正确地排除掉概率为0的选择。 - ninjagecko>>> weighted_choices = [('Red', 3), ('Blue', 2), ('Yellow', 1), ('Green', 4)]
>>> population = [val for val, cnt in weighted_choices for i in range(cnt)]
>>> random.choice(population)
'Green'
更一般的方法是使用itertools.accumulate()将权重累积到累积分布中，然后使用bisect.bisect()定位随机值:
>>> choices, weights = zip(*weighted_choices)
>>> cumdist = list(itertools.accumulate(weights))
>>> x = random.random() * cumdist[-1]
>>> choices[bisect.bisect(cumdist, x)]
'Blue'
import random
def selector(weights):
i=random.random()*sum(x for x,y in weights)
for w,v in weights:
if w>=i:
break
i-=w
return v
weights = ((70,'a'),(20,'b'),(10,'c'))
print [selector(weights) for x in range(10)]
它同样适用于分数重量
weights = ((0.7,'a'),(0.2,'b'),(0.1,'c'))
print [selector(weights) for x in range(10)]
如果你有很多权重要处理，可以使用二分法（bisect）来减少所需的迭代次数。
import random
import bisect
def make_acc_weights(weights):
acc=0
acc_weights = []
for w,v in weights:
acc+=w
acc_weights.append((acc,v))
return acc_weights
def selector(acc_weights):
i=random.random()*sum(x for x,y in weights)
return weights[bisect.bisect(acc_weights, (i,))][1]
weights = ((70,'a'),(20,'b'),(10,'c'))
acc_weights = make_acc_weights(weights)
print [selector(acc_weights) for x in range(100)]
对于分数权重也可以正常工作
weights = ((0.7,'a'),(0.2,'b'),(0.1,'c'))
acc_weights = make_acc_weights(weights)
print [selector(acc_weights) for x in range(100)]
如果你真的想快速生成随机值，而且已经掌握了相关技能，那么mcdowella在https://dev59.com/wnA65IYBdhLWcg3wvhXi#3655773中提到的Walker算法几乎是最好的选择（对于random()函数，时间复杂度为O(1)，对于预处理，时间复杂度为O(N)）。
对于任何感兴趣的人，这里是我自己实现的PHP版本：
/**
* Pre-process the samples (Walker's alias method).
* @param array key represents the sample, value is the weight
*/
protected function preprocess($weights){
$N = count($weights);
$sum = array_sum($weights);
$avg = $sum / (double)$N;
//divide the array of weights to values smaller and geq than sum/N
$smaller = array_filter($weights, function($itm) use ($avg){ return $avg > $itm;}); $sN = count($smaller);
$greater_eq = array_filter($weights, function($itm) use ($avg){ return $avg <= $itm;}); $gN = count($greater_eq);
$bin = array(); //bins
//we want to fill N bins
for($i = 0;$i<$N;$i++){
//At first, decide for a first value in this bin
//if there are small intervals left, we choose one
if($sN > 0){
$choice1 = each($smaller);
unset($smaller[$choice1['key']]);
$sN--;
} else{ //otherwise, we split a large interval
$choice1 = each($greater_eq);
unset($greater_eq[$choice1['key']]);
}
//splitting happens here - the unused part of interval is thrown back to the array
if($choice1['value'] >= $avg){
if($choice1['value'] - $avg >= $avg){
$greater_eq[$choice1['key']] = $choice1['value'] - $avg;
}else if($choice1['value'] - $avg > 0){
$smaller[$choice1['key']] = $choice1['value'] - $avg;
$sN++;
}
//this bin comprises of only one value
$bin[] = array(1=>$choice1['key'], 2=>null, 'p1'=>1, 'p2'=>0);
}else{
//make the second choice for the current bin
$choice2 = each($greater_eq);
unset($greater_eq[$choice2['key']]);
//splitting on the second interval
if($choice2['value'] - $avg + $choice1['value'] >= $avg){
$greater_eq[$choice2['key']] = $choice2['value'] - $avg + $choice1['value'];
}else{
$smaller[$choice2['key']] = $choice2['value'] - $avg + $choice1['value'];
$sN++;
}
//this bin comprises of two values
$choice2['value'] = $avg - $choice1['value'];
$bin[] = array(1=>$choice1['key'], 2=>$choice2['key'],
'p1'=>$choice1['value'] / $avg,
'p2'=>$choice2['value'] / $avg);
}
}
$this->bins = $bin;
}
/**
* Choose a random sample according to the weights.
*/
public function random(){
$bin = $this->bins[array_rand($this->bins)];
$randValue = (lcg_value() < $bin['p1'])?$bin[1]:$bin[2];
}
这是我适用于任何 IList 并规范化权重的版本。它基于 Timwi 的解决方案：基于百分比加权的选择。
/// <summary>
/// return a random element of the list or default if list is empty
/// </summary>
/// <param name="e"></param>
/// <param name="weightSelector">
/// return chances to be picked for the element. A weigh of 0 or less means 0 chance to be picked.
/// If all elements have weight of 0 or less they all have equal chances to be picked.
/// </param>
/// <returns></returns>
public static T AnyOrDefault<T>(this IList<T> e, Func<T, double> weightSelector)
{
if (e.Count < 1)
return default(T);
if (e.Count == 1)
return e[0];
var weights = e.Select(o => Math.Max(weightSelector(o), 0)).ToArray();
var sum = weights.Sum(d => d);
var rnd = new Random().NextDouble();
for (int i = 0; i < weights.Length; i++)
{
//Normalize weight
var w = sum == 0
? 1 / (double)e.Count
: weights[i] / sum;
if (rnd < w)
return e[i];
rnd -= w;
}
throw new Exception("Should not happen");
}