2

For example, I want to get random number from set S = {0, 1, 2, 3}. But instead of each number has same probability to shown (which is 25%), now I have different probability for each number, let say {50%, 30%, 20%, 10%}. How do I code this? In Java or C# (I prefer C#).

Agung Pratama
  • 3,666
  • 7
  • 36
  • 77

2 Answers2

3

The Alias Method is by far my favorite for doing this.

http://code.activestate.com/recipes/576564-walkers-alias-method-for-random-objects-with-diffe/

I haven't reviewed this code but it is a top google result.

Here is another much better explanation

http://pandasthumb.org/archives/2012/08/lab-notes-the-a.html

I actually use this question for interviews quite often since if you have never seen it before it can be pretty puzzling.

If the above is too much for you to implement there is a simpler one loop through the input solution.

Using PHP since it is easier to just show the code.

function getNumberFromDistribution($dist) {
    $totalProbability = 0;
    $randomNumber = mt_rand(0, mt_getrandmax()) / mt_getrandmax();  //uniform random number between 0-1
    foreach($dist as $number => $chance) {
        if (($totalProbability += $chance) <= $randomNumber) {
            return $number;
        }
    }

    return null; //only reachable on bad input
}
Daniel Williams
  • 8,673
  • 4
  • 36
  • 47
0

If the set is small you can build an array that contains the right number of each value you need to get your distribution eg. 1 1 1 2 2 3 would provide 3 times the likelihood of getting a 1 as it does of getting a 3. You would then use the length of the array to determine the random number that you use as an index.

Peter Wooster
  • 6,009
  • 2
  • 27
  • 39
  • Please explain your downvote. – Peter Wooster Mar 06 '13 at 02:24
  • I have thought that way before, but unfortunately the range number is quite big. Another way that i thought is to normalize the percentage to discrete number like {0.2, 0.71, 0.29} -> {20, 71, 29}. And get random number from 0-100. if rand>0.2 and rand<=0.91, then the 2nd number is choosed. But I dont think this is a good idea though. – Agung Pratama Mar 06 '13 at 02:25
  • This is one of the standard solutions to this problem. Note that I started by saying "if the set is small" – Peter Wooster Mar 06 '13 at 02:28
  • 1
    If the set is small I can still give an input that will allocate all available memory. 0.00000001% => 1, 99.99999999% => 2. – Daniel Williams Mar 06 '13 at 02:30
  • This solution is also very fast if the distribution can be compiled into the code. It does require a lot of memory if the set is arge. – Peter Wooster Mar 06 '13 at 02:31
  • @daniel yes, and you wouldn't use it in that case. – Peter Wooster Mar 06 '13 at 02:33
  • @daniel note that the question stated 50% 30% 20% 10% which can be done with an 11 element array. – Peter Wooster Mar 06 '13 at 02:39
  • There is no absolutely no good reason to use this method. It is not "one of the standard solutions to this problem". It is brute force and fragile. – Mitch Wheat Mar 06 '13 at 02:46