CODEWITHSUNDEEP
c#logic
Febin J S
Febin J S

Reputation: 1368

Selecting random item from list having probability weighting using c#?

I have a scenario where i a was taking a list of users (20 users) from my database, where i was giving weighting for users

first 5 users probability factor of 4 next 5 users probability factor of 3 next 5 users probability factor of 2 next 5 users probability factor of 1

So an user that occurs in the first 5 users is 4 times more likely to occur than an user in the last 5.

So how can i select a random user from the list using probability in c#? can anybody help me in doing this i am totally stuck up logically?

Upvotes: 2

Views: 1773

Answers (5)

El Ronnoco
El Ronnoco

Reputation: 11922

You could apportion the probability range amongst the users using a dictionary. eg

User 1 has 1-4 (so max of 4)

User 2 has 5-8 (max of 8) etc etc...

Then after selecting the random number find which user within the dictionary it relates to. You can do this using Linq like so...

int iUser = users.Where(p => (choice <= p.Value)).First().Key;

..where users is a Dictionary<int,int> (Key = user number, Value = max value) and choice is the randomly generated value.

This is obviously more complex than the "multiple entries" method proposed by others but has its advantages if you

a) need a fractional weighting which makes the common denominator of your multiple entry method very small (resulting in many entries) or

b) need to weight heavily in favour of particular users (which would again have the effect of making the multiple entry method very large).

Working Example at ideone.

Upvotes: 1

Alexey Romanov
Alexey Romanov

Reputation: 170745

Create a list of partial sums of weights. In your example, it would be

[4, 8, 12, 16, 20, 23, ...]

The last element is the sum of all weights. Pick a random number between 0 and this sum (exclusive). Then your element is the first element with partial sum greater then the random number. So if you got 11, you need the third element, if you got 16, the fifth, etc.

Upvotes: 4

Mihalis Bagos
Mihalis Bagos

Reputation: 2510

One solution would be to find the smallest common denominator of the weights (or just multiply them together) and create a new list that contains the keys of the first list, but multiple times, ie:

user1 user1 user2 user3 user3 user3

Then just to a newList.skip(Random.Next(newList.Count)).Take(1) and you are set!

Upvotes: 1

GuyVdN
GuyVdN

Reputation: 692

You could add the uses the number of probability times in the list. So the 5 first users are 4 times in the list, next 5 users 3 times and so on. Then just select one user from the complete list.

Upvotes: 4

Fischermaen
Fischermaen

Reputation: 12458

I have a (bit hacky) solution for you:

Create a list containing the users, where each user is added as often as his weightage is. (e.g. User has a weightage of 5, add him 5 times to the list). Then us a Random to fetch a user from that list, that should solve your problem.

Upvotes: 1

Related Questions