1

I am receiving a List<Fruit> of unkown size, usually between 4-10 items:

{ Apples, Orange, Pear, ?, ?, ... }

How can I weight the List in a way that Apples have the highest % chance of being selected, then Orange, then Pear?

The effect should essentially be the same as picking a random item from a List that looks like this:

{ Apples, Apples, Apples, Apples, Orange, Orange, Pear }

If the List was of a fixed size, I would've done

  1. Generate a float between 0.0-1.0;
  2. If < 0.4, return Apples. Else if < 0.75 return Orange etc.

Note that this question is not about selecting a random item from a weighted list but about weighting an existing List of arbitrary length in a way that a random pick will result in an Item's probability of being picked proportional to its position in the List.

vzwick
  • 11,008
  • 5
  • 43
  • 63
SirMt
  • 38
  • 5
  • 2
    Have you tried implementing the "effect" that you mention at the end? – Nathan Werry Dec 03 '18 at 00:29
  • 1
    You have the right idea. Just create a *weighting function" that you can use to adjust the weights any way you want – Flydog57 Dec 03 '18 at 00:34
  • This is a very useful question, but your title was going to lower its searchability (and therefore, future usefulness) substantially. – jonsca Dec 03 '18 at 00:36
  • 1
    Hi Nathan I haven't tried implementing the {Apple, Apple, Orange} method because I have 15 types of fruits and it'll probably hard to read - to interpret what % chance each item has - and tweaking the % when the List becomes longer – SirMt Dec 03 '18 at 00:53
  • Not a duplicate - the other question is concerned with selecting a random element from a *pre-weighted* set, this one is concerned with *weighting* a set. – vzwick Dec 03 '18 at 01:27
  • @vzwick please edit question to reflect that (don't forget to edit in link to the current duplicate) and ping me to re-open. Also make sure it matches your answer (i.e. "weights must be going as powers of two" or something like that) – Alexei Levenkov Dec 03 '18 at 03:53
  • @AlexeiLevenkov - Good suggestions. Ping ;) – vzwick Dec 03 '18 at 13:01

1 Answers1

2
var weightedItems = myList
    .Select((item, index)
        => new { Item = item, Weight = 1f / Math.Pow(2, index) });

This will give you an IEnumerable of tuples of the Item and a Weight that gets smaller as the Item's index increases. I.e:

Item = Apples, Weight = 1
Item = Orange, Weight = 0.5
Item = Pear  , Weight = 0.25

etc.

You can obviously tune the 1f / Math.Pow(2, index) part (which calculates the weight) to your liking. The one I used has the nice-ish side effect of yielding 1 >= n > 0 which is a predictable range and making each item half as likely to get picked as the previous one.

Selecting a random item from this structure according to your requirement could be done like this:

  • Generate a random number between 1 and 0
  • Iterate the IEnumerable from lowest to highest Weight
  • Return the first item where Weight >= your random number
vzwick
  • 11,008
  • 5
  • 43
  • 63
  • @SirMt I actually fudged up the weighting function on my first try - `1 / (index + 1)` makes the "choose the first element larger or equal to a random number between 0 and 1" approach more likely to return the 3rd element than the 2nd. The `Math.Pow` takes care of that. – vzwick Dec 03 '18 at 01:45
  • Both methods are fantastic starting points to tweak towards the behavior I wanted. Very helpful – SirMt Dec 03 '18 at 07:36