выбор на основе процентного веса

Question

У меня есть набор значений и связанный процент для каждого:

a: шанс 70%
б: вероятность 20%
с: 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

Свободно основано на numpy.random.choice(a=items, p=probs) Python, который принимает массив и массив вероятностей одинакового размера.

    public T RandomChoice<T>(IEnumerable<T> a, IEnumerable<double> p)
    {
        IEnumerator<T> ae = a.GetEnumerator();
        Random random = new Random();
        double target = random.NextDouble();
        double accumulator = 0;
        foreach (var prob in p)
        {
            ae.MoveNext();
            accumulator += prob;
            if (accumulator > target)
            {
                break;
            }
        }
        return ae.Current;
    }

Массив вероятностей p должен суммироваться до (приблизительно) 1. Это делается для того, чтобы поддерживать его согласованным с простым интерфейсом (и математикой), но вы можете легко изменить это, если хотите.

Answer 2

Вот моя версия, которая может применяться к любому IList и нормализовать вес. Он основан на решении Тимви: выбор на основе процентного веса

/// <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");
}

Answer 3

Если вы действительно разбираетесь в скорости и хотите быстро генерировать случайные значения, алгоритм mcdowella Уокера, упомянутый в https://stackoverflow.com/a/3655773/1212517, является в значительной степени наилучшим способом (O (1) время для random (),и 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];        
}