Picking at random, with varied probabilities

Hot Topic

Thread
which event has been raised
Value does not get assigned??
GetMethods(BindingFlags.Public) not returning anything
I need to acces flash memory device
Cancel Editing Form / Text Box Validating Event
Need help converting VB to C#
Unhandled exception only when running in release without debugger attached.
Dispose question
FontDialog show with wrong fornt size.

Visual C#

How to open Excel in the current folder using C#
Incorporate Java compiler in C#?
VS 2005 crashes when launching "Add Reference" dialog
[C#2005] Parsing data from and to a string
cs 5001 No Main method suitable for entry point
Timer Precision
Async Sockets
What is Reflection ?
private fields, public properties...why??
Problem to Build a project in C#

Picking at random, with varied probabilities

One part of a program that I'm writing requires me to pick an object at random out of a collection. Each object has a different weight (probability), currently stored as a Double, associated with it, and the number of objects varies. The total probability, 1.0, is equal to the sum of the weights of all the objects in the collection.

Is there a commonly used, efficient algorithm for picking random objects in this situation

Currently, the only one I can think of (and this is pretty tedious):
  1. Load the keys and weights of the collection's objects into structures inside an ArrayList.
  2. Sort the ArrayList in ascending order, by weight.
  3. Add on another value (CumulativeWeight) to each structure that represents the sum of all the weights up to and including that structure.
  4. Pick a number at random between zero and the last CumulativeWeight.
  5. Find the ArrayList element such that the random value is higher than its cumulative weight, but lower than that of the next element.

Answer this question

Picking at random, with varied probabilities

  • Nelson J

    Ah -- I meant that that P(any outcome) = 1.0, in standard math terms, since you can't have a probability greater than 1.
    In my program, however, P(any outcome) translates to the sum of all the weights, which can be greater than 1.

    Sorry I didn't phrase that correctly.

  • Jon Braganza

    That sounds about right, except there's no need to sort it by weight, and there's no need to sum the calculated weight beforehand. Just enumerate through the array once, added and comparing.


    double runningtotal = 0.0;
    double randValue = ....
    MyObj winningObj = null;
    foreach(MyObj obj in MyArray)
    {
    runningtotal += obj.Weight;
    if (runningtotal > randValue)
    {
    winningObj = obj;
    break;
    }
    }



  • gharen1234

    Thank you, that's perfect.
    I believe I do need a single sum of all of the weights in advance, though, since I need to know the range of the random number. But, that's trivial to implement, so it's not a problem.

  • techsavvy_pat

    I believe I do need a single sum of all of the weights in advance, though, since I need to know the range of the random number.

    You said that we know in advance that they add up to 1.0.

    The total probability, 1.0, is equal to the sum of the weights of all the objects in the collection.



  • Picking at random, with varied probabilities
Answer this question