отбора на основе процентного взвешивания

Question

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

: с 70% вероятностью
б: 20% шанс
C: 10% шанс

Я хочу выбрать значение (a, b, c) на основе процентного шанса.

Как подойти к этому?

моя попытка до сих пор выглядит следующим образом:

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

Я застрял придумывают алгоритма справиться с этим. Как мне подойти к этому, чтобы он мог обрабатывать более крупные наборы значений, не связывая друг с другом потоки if-else.

(любое объяснение или ответы в псевдокоде штраф реализация питона или C# будет особенно полезно.)

Answer 1

Возьмите список и найти нарастающий итог весов: 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 }) 

Это решение, как это реализовано, также должны быть в состоянии обрабатывать дробные веса и веса, которые складываются на любое число, если все они неотрицательны.

Answer 2

Я думаю, что у вас может быть массив небольших объектов (я реализовал на Java, хотя знаю немного C#, но я боюсь, что могу написать неправильный код), поэтому вам может понадобиться его самостоятельно портировать. Код в C# будет гораздо меньше с STRUCT, вар, но я надеюсь, что вы получите идею

class PercentString { 
    double percent; 
    String value; 
    // Constructor for 2 values 
} 

ArrayList<PercentString> list = new ArrayList<PercentString(); 
list.add(new PercentString(70, "a"); 
list.add(new PercentString(20, "b"); 
list.add(new PercentString(10, "c"); 

double percent = 0; 
for (int i = 0; i < list.size(); i++) { 
    PercentString p = list.get(i); 
    percent += p.percent; 
    if (random < percent) { 
    return p.value; 
    } 
} 

Answer 3

1. Пусть T = сумма всех весов элементов
2. Пусть R = случайное число между 0 и Т
3. итерацию списка элементов вычитанием каждого веса элемента из R и возвращает элемент, который вызывает результат стать < = 0.

Answer 4

для 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 5

Вот полное решение в 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 6

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 никогда не должно быть достигнуто ,

Answer 7

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)] 

Если у вас есть много весов, вы можете использовать разрез`ать, чтобы уменьшить число итераций требуется

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)] 

Answer 8

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/. Это дает точные вероятности, требуемые в постоянное время на число, генерируемое с линейным временем для установки (любопытно, n log n время для установки, если вы точно используете метод, описанный Knuth, который может быть подготовительным типом, который вы можете избежать).

Answer 9

сегодня, the update of python document привести пример, чтобы сделать random.choice() с взвешенными вероятностями:

Если веса представляют собой небольшие целые коэффициенты, простой метод заключается в создании популяции образца с повторами:

>>> 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' 

одна нота: itertools.accumulate() needs python 3.2 or define it with the Equivalent.

Answer 10

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

Answer 11

Вот моя версия, которая может применяться к любому IList и нормализовать вес.Он основан на решении Timwi в: selection based on percentage weighting

/// <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 12

Я свое собственное решение для этого:

public class Randomizator3000 
{  
public class Item<T> 
{ 
    public T value; 
    public float weight; 

    public static float GetTotalWeight<T>(Item<T>[] p_itens) 
    { 
     float __toReturn = 0; 
     foreach(var item in p_itens) 
     { 
      __toReturn += item.weight; 
     } 

     return __toReturn; 
    } 
} 

private static System.Random _randHolder; 
private static System.Random _random 
{ 
    get 
    { 
     if(_randHolder == null) 
      _randHolder = new System.Random(); 

     return _randHolder; 
    } 
} 

public static T PickOne<T>(Item<T>[] p_itens) 
{ 
    if(p_itens == null || p_itens.Length == 0) 
    { 
     return default(T); 
    } 

    float __randomizedValue = (float)_random.NextDouble() * (Item<T>.GetTotalWeight(p_itens)); 
    float __adding = 0; 
    for(int i = 0; i < p_itens.Length; i ++) 
    { 
     float __cacheValue = p_itens[i].weight + __adding; 
     if(__randomizedValue <= __cacheValue) 
     { 
      return p_itens[i].value; 
     } 

     __adding = __cacheValue; 
    } 

    return p_itens[p_itens.Length - 1].value; 

} 
} 

И используя это должно быть что-то подобное (то будет в Unity3d)

using UnityEngine; 
using System.Collections; 

public class teste : MonoBehaviour 
{ 
Randomizator3000.Item<string>[] lista; 

void Start() 
{ 
    lista = new Randomizator3000.Item<string>[10]; 
    lista[0] = new Randomizator3000.Item<string>(); 
    lista[0].weight = 10; 
    lista[0].value = "a"; 

    lista[1] = new Randomizator3000.Item<string>(); 
    lista[1].weight = 10; 
    lista[1].value = "b"; 

    lista[2] = new Randomizator3000.Item<string>(); 
    lista[2].weight = 10; 
    lista[2].value = "c"; 

    lista[3] = new Randomizator3000.Item<string>(); 
    lista[3].weight = 10; 
    lista[3].value = "d"; 

    lista[4] = new Randomizator3000.Item<string>(); 
    lista[4].weight = 10; 
    lista[4].value = "e"; 

    lista[5] = new Randomizator3000.Item<string>(); 
    lista[5].weight = 10; 
    lista[5].value = "f"; 

    lista[6] = new Randomizator3000.Item<string>(); 
    lista[6].weight = 10; 
    lista[6].value = "g"; 

    lista[7] = new Randomizator3000.Item<string>(); 
    lista[7].weight = 10; 
    lista[7].value = "h"; 

    lista[8] = new Randomizator3000.Item<string>(); 
    lista[8].weight = 10; 
    lista[8].value = "i"; 

    lista[9] = new Randomizator3000.Item<string>(); 
    lista[9].weight = 10; 
    lista[9].value = "j"; 
} 


void Update() 
{ 
    Debug.Log(Randomizator3000.PickOne<string>(lista)); 
} 
} 

В этом примере каждое значение имеет 10% -ный шанс быть отображенным как отладка = 3

Answer 13

Вот рубин версия методы псевдонимов, а также: https://github.com/cantino/walker_method