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

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

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

Answer 4

This could work:

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

Basically, for each element a partition is created with an end weight. In your example, Element1 would associated to (1-->100), Element2 associated to (101-->151) and so on...

Then a random weight sum is calculated and we look for the range which is associated to it.

You could also compute the sum in the method group but that would introduce another side effect...

Note that I'm not saying this is elegant or fast. But it does use linq (not in one line...)

Answer 5

.Net 6 introduced .MaxBy making this much easier.
This could now be simplified to the following one-liner:

list.MaxBy(x => rng.GetNext(x.weight));

This works best if the weights are large or floating point numbers, otherwise there will be collisions, which can be prevented by multiplying the weight by some factor.