Whats the most concise way to pick a random element by weight in c#?

Question

Lets assume:

List<element> which element is:

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

What I want to achieve is, select an element randomly by the weight. For example:

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

So

• the chance Element_1 got selected is 100/(100+50+200)=28.57%
• the chance Element_2 got selected is 50/(100+50+200)=14.29%
• the chance Element_3 got selected is 200/(100+50+200)=57.14%

I know I can create a loop, calculate total, etc...

What I want to learn is, whats the best way to do this by Linq in ONE line (or as short as possible), thanks.

UPDATE

I found my answer below. First thing I learn is: Linq is NOT magic, it's slower then well-designed loop.

So my question becomes find a random element by weight, (without as short as possible stuff :)

Answer 1

// 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 2

If you want a generic version (useful for using with a (singleton) randomize helper, consider whether you need a constant seed or not)

usage:

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

code:

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 3

This is a fast solution with precomputation. The precomputation takes O(n), the search O(log(n)).

Precompute:

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;
}

To generate:

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];

---

But if the list changes between each search, you can instead use a simple O(n) linear search:

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;
}