Números aleatorios ponderados

Estoy tratando de implementar números aleatorios ponderados. Actualmente me estoy golpeando la cabeza contra la pared y no puedo entender esto.

En mi proyecto (rangos de manos de Hold'em, análisis de equidad todo incluido subjetivo), estoy usando las funciones aleatorias de Boost. Entonces, digamos que quiero elegir un número aleatorio entre 1 y 3 (por lo tanto, 1, 2 o 3). El generador de tornado de mersenne de Boost funciona de maravilla para esto. Sin embargo, quiero que la selección sea ponderada, por ejemplo, así:

1 (weight: 90)
2 (weight: 56)
3 (weight:  4)

¿Boost tiene algún tipo de funcionalidad para esto?

Existe un algoritmo sencillo para seleccionar un artículo al azar, donde los artículos tienen pesos individuales:

1) calcula la suma de todos los pesos

2) elija un número aleatorio que sea 0 o mayor y sea menor que la suma de los pesos

3) revise los artículos uno a la vez, restando su peso de su número aleatorio, hasta que obtenga el artículo donde el número aleatorio es menor que el peso de ese artículo

Pseudocódigo que ilustra esto:

int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];
}
assert(!"should never get here");

Esto debería ser sencillo de adaptar a sus contenedores de impulso y demás.

Si sus pesos rara vez se cambian, pero a menudo elige uno al azar, y siempre que su contenedor esté almacenando punteros a los objetos o tenga más de unas pocas docenas de elementos (básicamente, debe perfilar para saber si esto ayuda o dificulta) , luego hay una optimización:

Al almacenar la suma de peso acumulada en cada artículo, puede utilizar una búsqueda binaria para seleccionar el artículo correspondiente al peso de picking.

Si no conoce la cantidad de elementos de la lista, existe un algoritmo muy ordenado llamado muestreo de yacimientos que se puede adaptar para ponderar.

Respuesta actualizada a una pregunta anterior. Puede hacer esto fácilmente en C ++ 11 con solo std :: lib:

#include <iostream>
#include <random>
#include <iterator>
#include <ctime>
#include <type_traits>
#include <cassert>

int main()
{
    // Set up distribution
    double interval[] = {1,   2,   3,   4};
    double weights[] =  {  .90, .56, .04};
    std::piecewise_constant_distribution<> dist(std::begin(interval),
                                                std::end(interval),
                                                std::begin(weights));
    // Choose generator
    std::mt19937 gen(std::time(0));  // seed as wanted
    // Demonstrate with N randomly generated numbers
    const unsigned N = 1000000;
    // Collect number of times each random number is generated
    double avg[std::extent<decltype(weights)>::value] = {0};
    for (unsigned i = 0; i < N; ++i)
    {
        // Generate random number using gen, distributed according to dist
        unsigned r = static_cast<unsigned>(dist(gen));
        // Sanity check
        assert(interval[0] <= r && r <= *(std::end(interval)-2));
        // Save r for statistical test of distribution
        avg[r - 1]++;
    }
    // Compute averages for distribution
    for (double* i = std::begin(avg); i < std::end(avg); ++i)
        *i /= N;
    // Display distribution
    for (unsigned i = 1; i <= std::extent<decltype(avg)>::value; ++i)
        std::cout << "avg[" << i << "] = " << avg[i-1] << '\n';
}

Salida en mi sistema:

avg[1] = 0.600115
avg[2] = 0.373341
avg[3] = 0.026544

Tenga en cuenta que la mayor parte del código anterior está dedicado solo a mostrar y analizar la salida. La generación real son solo unas pocas líneas de código. El resultado demuestra que se han obtenido las "probabilidades" solicitadas. Debe dividir la salida solicitada por 1.5, ya que eso es lo que suman las solicitudes.

Si sus pesos cambian más lentamente de lo que se dibujan, C ++ 11 discrete_distributionserá el más fácil:

#include <random>
#include <vector>
std::vector<double> weights{90,56,4};
std::discrete_distribution<int> dist(std::begin(weights), std::end(weights));
std::mt19937 gen;
gen.seed(time(0));//if you want different results from different runs
int N = 100000;
std::vector<int> samples(N);
for(auto & i: samples)
    i = dist(gen);
//do something with your samples...

Sin embargo, tenga en cuenta que c ++ 11 discrete_distributioncalcula todas las sumas acumulativas en la inicialización. Por lo general, lo desea porque acelera el tiempo de muestreo por un costo O (N) único. Pero para una distribución que cambia rápidamente, incurrirá en un alto costo de cálculo (y memoria). Por ejemplo, si los pesos representan la cantidad de elementos que hay y cada vez que dibuja uno, lo elimina, probablemente querrá un algoritmo personalizado.

La respuesta de Will https://stackoverflow.com/a/1761646/837451 evita esta sobrecarga, pero será más lenta de extraer que C ++ 11 porque no puede usar la búsqueda binaria.

Para ver que hace esto, puede ver las líneas relevantes ( /usr/include/c++/5/bits/random.tccen mi instalación de Ubuntu 16.04 + GCC 5.3):

  template<typename _IntType>
    void
    discrete_distribution<_IntType>::param_type::
    _M_initialize()
    {
      if (_M_prob.size() < 2)
        {
          _M_prob.clear();
          return;
        }

      const double __sum = std::accumulate(_M_prob.begin(),
                                           _M_prob.end(), 0.0);
      // Now normalize the probabilites.
      __detail::__normalize(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
                            __sum);
      // Accumulate partial sums.
      _M_cp.reserve(_M_prob.size());
      std::partial_sum(_M_prob.begin(), _M_prob.end(),
                       std::back_inserter(_M_cp));
      // Make sure the last cumulative probability is one.
      _M_cp[_M_cp.size() - 1] = 1.0;
    }

Lo que hago cuando necesito ponderar números es usar un número aleatorio para el peso.

Por ejemplo: necesito generar números aleatorios del 1 al 3 con los siguientes pesos:

• 10% de un número aleatorio podría ser 1
• 30% de un número aleatorio podría ser 2
• 60% de un número aleatorio podría ser 3

Entonces uso:

weight = rand() % 10;

switch( weight ) {

    case 0:
        randomNumber = 1;
        break;
    case 1:
    case 2:
    case 3:
        randomNumber = 2;
        break;
    case 4:
    case 5:
    case 6:
    case 7:
    case 8:
    case 9:
        randomNumber = 3;
        break;
}

Con esto, aleatoriamente tiene un 10% de probabilidades de ser 1, 30% de ser 2 y 60% de ser 3.

Puedes jugar con él según tus necesidades.

Espero poder ayudarte, ¡buena suerte!

Construya una bolsa (o std :: vector) de todos los elementos que se pueden recoger.
Asegúrese de que el número de cada artículo sea proporcional a su ponderación.

Ejemplo:

• 1 60%
• 2 35%
• 3 5%

Así que tenga una bolsa con 100 artículos con 60 1, 35 2 y 5 3.
Ahora ordena aleatoriamente la bolsa (std :: random_shuffle)

Elija elementos de la bolsa secuencialmente hasta que esté vacía.
Una vez vacía, vuelva a aleatorizar la bolsa y comience de nuevo.

Elija un número aleatorio en [0,1), que debería ser el operador predeterminado () para un aumento de RNG. Elija el elemento con la función de densidad de probabilidad acumulada> = ese número:

template <class It,class P>
It choose_p(It begin,It end,P const& p)
{
    if (begin==end) return end;
    double sum=0.;
    for (It i=begin;i!=end;++i)
        sum+=p(*i);
    double choice=sum*random01();
    for (It i=begin;;) {
        choice -= p(*i);
        It r=i;
        ++i;
        if (choice<0 || i==end) return r;
    }
    return begin; //unreachable
}

Donde random01 () devuelve un doble> = 0 y <1. Tenga en cuenta que lo anterior no requiere que las probabilidades sumen 1; los normaliza para ti.

p es simplemente una función que asigna una probabilidad a un elemento de la colección [inicio, finalización]. Puede omitirlo (o usar una identidad) si solo tiene una secuencia de probabilidades.

Implementé varios algoritmos aleatorios ponderados simples .