2010-06-30 10 views
5

Tengo un requisito en mi proyecto .net donde tengo que seleccionar un elemento de una colección, cada elemento tiene un peso (número entero de 1 a 10) asignado a él. Necesito un generador aleatorio que tenga en cuenta este peso, es decir, cuanto mayor sea el peso, mayores serán las posibilidades de que se seleccione el objeto. Se aprecian los ejemplos de código en .net, aunque la descripción del algoritmo también es agradable.Necesito algoritmo aleatorio con opciones de pesaje en .net

Editar: copia rápida/pega código C# en caso de que alguien se tropiece con esto.

class RandomWeightedSelector<T> 
    { 
     private List<T> items = new List<T>(); 

     public void Add(T item, uint weight = 1) 
     { 
      for (int i = 0; i < weight; i++) 
       items.Add(item); 
     } 

     public T GetRandom() 
     { 
      return items[new Random().Next(0, items.Count)]; 
     } 
    } 
+1

Usted no quiere ser la creación de un nuevo aleatoria cada llamada a 'GetRandom'. El constructor predeterminado para 'Random' siembra el generador con el tiempo de actividad del sistema en milisegundos. Si llama a su 'GetRandom' más de una vez por milisegundo, se le devolverá el mismo valor. Incluso si no lo hace, podría estar devolviendo resultados que tienen peor 'aleatoriedad' que simplemente reutilizar una sola instancia 'Random'. – Dolphin

Respuesta

8

Aquí hay un algoritmo que no requiere agregar los elementos varias veces a una lista. También puede funcionar con pesos no enteros, aunque si usa NextDouble de System.Random, tendrá que escalar todos los pesos para agregar hasta 1, o multiplicar el valor de NextDouble con S para obtenerlo el rango deseado

dado una lista de elementos L (I, W), donde I es el elemento y W es el peso:

  1. añadir todos los pesos juntos. Llame a esta suma S.
  2. Genere un número aleatorio entre 0 y S (excluyendo S, pero incluido 0). Llame a este valor R.
  3. Inicialice una variable en 0 para realizar un seguimiento del total acumulado. Llamaremos a este T.
  4. Para cada elemento (I, W) en L:
    1. T = T + W
    2. Si T> R, vuelva I.
+0

En lugar de escalar sus pesos, puede usar 'NextDouble() * S' –

+0

@Justin: Sí, eso también funcionaría. Actualicé mi publicación en consecuencia. –

4

Haga una lista e inserte cada elemento en Número de veces. Luego elige un elemento al azar de la lista.

+0

Gracias, eso fue simple :) –

+1

Cabe señalar que esto funciona porque sus pesos siempre serán enteros. –

+0

Sí, eso es un requisito. El peso siempre será entero y al menos 1. El límite máximo de peso no es importante, parece. –

1

Lo que está buscando se llama el algoritmo del Selector ponderado. De hecho, ¡creé un proyecto de código abierto C# para esto hace algún tiempo!

Es muy fácil de usar y eficiente. Además, la documentación debe ayudarte sin problemas.

Éstos son algunos enlaces:

Cuestiones relacionadas