logo标签列表

基于百分比加权的选择

c#pythonalgorithmrandom
29

我有一组值，每个值都有一个对应的百分比：

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#实现的解释都可以。）

我曾经遇到过这个问题，最终建立了一个库：https://github.com/kinetiq/Ether.WeightedSelector - Brian MacKay
这里有一个非常好的、简单的C#实现： http://www.vcskicks.com/random-element.php - Roboblob
13个回答
1

我认为你可以拥有一个小对象的数组（我在Java中实现了，虽然我知道一点C#，但我担心会写错代码），所以你可能需要自己进行移植。使用结构体和变量，C#中的代码将更加简洁，但我希望你能理解这个想法。

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;
  }
}
抱歉误解了需求，我已经修改了我的代码。 - vodkhang
你的 random 是从哪里来的？ - daydreamer
1
我有自己的解决方案：
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%的机会被显示为debug = 3。
0

这个函数的设计灵感来自于Python中的numpy.random.choice(a=items, p=probs)，它接受一个数组和一个相同大小的概率数组。

    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。这是为了与numpy接口（和数学）保持一致，但如果您想要的话，可以轻松更改它。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接