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

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

Вот полное решение в 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 элементов с точно таким же поведением), но вы можете разделить все подсчеты в списке вероятностей по их наибольшему общему фактору, если вы считаете, что это может иметь большое значение в вашем конкретном сценарии применения.

Помимо проблем с потреблением памяти, это должно быть самое быстрое решение - всего одно генерирование случайного числа на требуемый выходной результат и максимально быстрый поиск из этого случайного числа, без сравнений и т. Д. Если ваши вероятные вероятности очень странные (например, числа с плавающей запятой, которые должны быть сопоставлены со многими, многими значащими цифрами), другие подходы могут быть предпочтительнее; -).

Answer 3

Кнут ссылается на псевдонимы Уокера. В поисках этого я нахожу 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 время для настройки, если вы используете точно метод, описанный Кнутом, который делает подготовительную сортировку, которую вы можете избежать).

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

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

Answer 5

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

Answer 6

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

Answer 7

сегодня, обновление документа Python приведите пример для создания 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 () требует Python 3.2 или определяет его с помощью Эквивалента.

Answer 8

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

Answer 9

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

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 10

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

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;
  }
}