Números aleatorios ponderados

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?

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

1) calcule la sum de todos los pesos

2) elija un número aleatorio que sea 0 o mayor y que sea menor que la sum 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 

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 sum 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.

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

 #include  #include  #include  #include  #include  #include  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::value] = {0}; for (unsigned i = 0; i < N; ++i) { // Generate random number using gen, distributed according to dist unsigned r = static_cast(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::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 sumn las solicitudes.

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!

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  #include  std::vector weights{90,56,4}; std::discrete_distribution 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 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 sums 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://stackoverflow.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 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; } 

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.

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

Implementé varios algoritmos aleatorios ponderados simples .