c++ - suma - numeros aleatorios en turbo c

Números aleatorios ponderados

Question

Estoy tratando de implementar un número aleatorio ponderado. Actualmente estoy golpeando mi cabeza contra la pared y no puedo resolver esto.

En mi proyecto (rangos de manos de Hold''em, análisis de equity subjetivo todo incluido), estoy usando las funciones al azar de Boost. Entonces, digamos que quiero elegir un número aleatorio entre 1 y 3 (por lo tanto, 1, 2 o 3). El generador Twister Twister de Boost funciona como un encanto 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?

Answer 1

Construye una bolsa (o std :: vector) de todos los artículos 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''s, 35 2''s y 5 3''s.
Ahora ordena al azar la bolsa (std :: random_shuffle)

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

Answer 2

Elija un número aleatorio en [0,1), que debería ser el operador predeterminado () para un impulso 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 se sumen a 1; los normaliza por ti.

p es solo una función que asigna una probabilidad a un elemento en la colección [inicio, fin]. Puedes omitirlo (o usar una identidad) si solo tienes una secuencia de probabilidades.

Answer 3

Hay un algoritmo sencillo para elegir un elemento al azar, donde los artículos tienen pesos individuales:

1) calcule la suma de todos los pesos

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

3) examine los ítems de a uno por vez, restando su peso de su número aleatorio, hasta que obtenga el ítem donde el número aleatorio es menor que el peso de ese ítem

Pseudo-có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 para adaptarse a sus contenedores de impulso y tal.

Si tus pesos rara vez cambian, a menudo eliges uno al azar, y mientras el contenedor esté almacenando punteros a los objetos o hay más de unas pocas docenas de artículos de largo (básicamente, tienes que hacer un perfil para saber si esto ayuda o dificulta) , entonces hay una optimización:

Al almacenar la suma de peso acumulada en cada artículo, puede usar una búsqueda binaria para elegir el artículo correspondiente al peso de recolección.

Si no conoce la cantidad de elementos en la lista, existe un algoritmo muy preciso llamado muestreo de yacimientos que puede adaptarse para ser ponderado.

Answer 4

Implementé varios algoritmos aleatorios ponderados simples .

Answer 5

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

Luego 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 10% de las probabilidades para ser 1, 30% para ser 2 y 60% para ser 3.

Puedes jugar con eso según tus necesidades.

Espero poder ayudarte, buena suerte!

Answer 6

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 a solo mostrar y analizar la salida. La generación real es 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 a lo que se suman las solicitudes.

Answer 7

Si sus pesos cambian más lentamente de lo que se dibujan, la distribución discrete_distribution C ++ 11 será la 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...

Tenga en cuenta, sin embargo, que el c ++ 11 discrete_distribution calcula todas las sumas acumuladas en la inicialización. Por lo general, lo desea porque acelera el tiempo de muestreo para un costo O (N) único. Pero para una distribución que cambia rápidamente, incurrirá en un gran costo de cálculo (y de memoria). Por ejemplo, si los pesos representan la cantidad de elementos que hay y cada vez que dibuja uno, lo elimina, es probable que desee un algoritmo personalizado.

La respuesta de Will https://.com/a/1761646/837451 evita esta sobrecarga pero será más lenta de dibujar 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.tcc en mi instalación 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;
    }