¿Cuál es la forma más concisa de elegir un elemento aleatorio por peso en C#?

Question

Asumamos:

List<element> qué elemento es:

public class Element(){ 
    int Weight {get;set;} 
} 

Lo que quiero lograr es, seleccione un elemento al azar por el peso. Por ejemplo:

Element_1.Weight = 100; 
Element_2.Weight = 50; 
Element_3.Weight = 200; 

Así

• la oportunidad Element_1 fue seleccionado es 100/(100 + 50 + 200) = 28,57%
• la oportunidad Element_2 fue seleccionado es 50/(100 + 50 + 200) = 14,29%
• la ocasión fue seleccionado Element_3 es de 200/(100 + 50 + 200) = 57,14%

Sé que puedo crear un bucle, calcular el total, etc ...

Lo que quiero aprender es cuál es la mejor manera de hacer esto con Linq en UNA línea (o lo más corto posible), gracias.

ACTUALIZACIÓN

encontré mi respuesta a continuación. Lo primero que aprendo es: Linq NO es mágico, es más lento que el ciclo bien diseñado.

Así que mi pregunta es encontrar un elemento aleatorio en peso, (sin lo más corto posible cosas :)

Answer 1

Si quieres un versión genérica (útil para usar con un (Singleton) aleatorizar ayudante, considerar si usted necesita una semilla constante o no)

uso:

randomizer.GetRandomItem(items, x => x.Weight) 

código:

public T GetRandomItem<T>(IEnumerable<T> itemsEnumerable, Func<T, int> weightKey) 
{ 
    var items = itemsEnumerable.ToList(); 

    var totalWeight = items.Sum(x => weightKey(x)); 
    var randomWeightedIndex = _random.Next(totalWeight); 
    var itemWeightedIndex = 0; 
    foreach(var item in items) 
    { 
     itemWeightedIndex += weightKey(item); 
     if(randomWeightedIndex < itemWeightedIndex) 
      return item; 
    } 
    throw new ArgumentException("Collection count and weights must be greater than 0"); 
} 

Answer 2

// assuming rnd is an already instantiated instance of the Random class 
var max = list.Sum(y => y.Weight); 
var rand = rnd.Next(max); 
var res = list 
    .FirstOrDefault(x => rand >= (max -= x.Weight)); 

Answer 3

Ésta es una solución rápida con precomputation. La precomputación toma O(n), la búsqueda O(log(n)).

precomputamos:

int[] lookup=new int[elements.Length]; 
lookup[0]=elements[0].Weight-1; 
for(int i=1;i<lookup.Length;i++) 
{ 
    lookup[i]=lookup[i-1]+elements[i].Weight; 
} 

Generar:

int total=lookup[lookup.Length-1]; 
int chosen=random.GetNext(total); 
int index=Array.BinarySearch(lookup,chosen); 
if(index<0) 
    index=~index; 
return elements[index]; 

---

Pero si la lista cambia entre cada búsqueda, en su lugar puede utilizar un simple O(n) búsqueda lineal:

int total=elements.Sum(e=>e.Weight); 
int chosen=random.GetNext(total); 
int runningSum=0; 
foreach(var element in elements) 
{ 
    runningSum+=element.Weight; 
    if(chosen<runningSum) 
    return element; 
} 

Answer 4

Esto podría funcionar:

int weightsSum = list.Sum(element => element.Weight); 
int start = 1; 
var partitions = list.Select(element => 
       { 
        var oldStart = start; 
        start += element.Weight; 
        return new { Element = element, End = oldStart + element.Weight - 1}; 
       }); 

var randomWeight = random.Next(weightsSum); 
var randomElement = partitions.First(partition => (partition.End > randomWeight)). 
           Select(partition => partition.Element); 

B asically, para cada elemento se crea una partición con un peso final. En su ejemplo, Element1 estaría asociado a (1 -> 100), Element2 asociado a (101 -> 151) y así sucesivamente ...

Luego se calcula una suma de peso aleatoria y buscamos el rango que está asociado a él.

También puede calcular la suma en el grupo método, sino que introduciría otro efecto secundario ...

Tenga en cuenta que no estoy diciendo que esto sea elegante o rápido. Pero sí utiliza linq (no en una línea ...)