CODEWITHSUNDEEP
algorithm
Ash Burlaczenko
Ash Burlaczenko

Reputation: 25435

What algorithm can I use to produce 'Random' value?

Say I have 4 possible results and the probabilities of each result appearing are

1 = 10%
2 = 20%
3 = 30%
4 = 40%

I'd like to write a method like GetRandomValue which if called 1000 times would return 

1 x 100 times
2 x 200 times
3 x 300 times
4 x 400 times

Whats the name of an algorithm which would produce such results?

Upvotes: 1

Views: 118

Answers (3)

DeCaf
DeCaf

Reputation: 6086

To get a random number you would use the Random class of .Net.

Something like the following would accomplish what you requested:

public class MyRandom
{
   private Random m_rand = new Random();

   public int GetNextValue()
   {         
      // Gets a random value between 0-9 with equal probability
      // and converts it to a number between 1-4 with the probablities requested.
      switch (m_rand.Next(0, 9))
      {
         case 0:
            return 1;
         case 1: case 2:
            return 2;
         case 3: case 4: case 5:
            return 3;
         default:
            return 4;               
      }    
   }
}

Upvotes: 1

Vlad
Vlad

Reputation: 18633

If you just want those probabilities in the long run, you can just get values by randomly selecting one element from the array {1,2,2,3,3,3,4,4,4,4}.

If you however need to retrieve exactly 1000 elements, in those specific quantities, you can try something like this (not C#, but shouldn't be a problem):

import java.util.Random;
import java.util.*;
class Thing{

    Random r = new Random();
    ArrayList<Integer> numbers=new ArrayList<Integer>();
    ArrayList<Integer> counts=new ArrayList<Integer>();
    int totalCount;

    public void set(int i, int count){    
        numbers.add(i);
        counts.add(count);
        totalCount+=count;
    }

    public int getValue(){
        if (totalCount==0)
            throw new IllegalStateException();

        double pos = r.nextDouble();

        double z = 0;
        int index = 0;

        //we select elements using their remaining counts for probabilities
        for (; index<counts.size(); index++){
            z += counts.get(index) / ((double)totalCount);
            if (pos<z)
                break;
        }

        int result = numbers.get(index);

        counts.set( index , counts.get(index)-1);
        if (counts.get(index)==0){
            counts.remove(index);
            numbers.remove(index);
        }
        totalCount--;

        return result;    
    }

}    

class Test{

    public static void main(String []args){

        Thing t = new Thing(){{
            set(1,100);
            set(2,200);
            set(3,300);
            set(4,400);
        }};

        int[]hist=new int[4];
        for (int i=0;i<1000;i++){
            int value = t.getValue();
            System.out.print(value);
            hist[value-1]++;
        }
        System.out.println();        

        double sum=0;
        for (int i=0;i<4;i++) sum+=hist[i];
        for (int i=0;i<4;i++)
            System.out.printf("%d: %d values, %f%%\n",i+1,hist[i], (100*hist[i]/sum));

    }

}

Upvotes: 0

Saeed Amiri
Saeed Amiri

Reputation: 22555

in your case you can generate a random number (int) within 1..10 and if it's 1 then select 1, if it's between 2-3 select 2 and if it's between 4..6 select 3 and if is between 7..10 select 4.

In all if you have some probabilities which sum to 1, you can have a random number within (0,1) distribute your generated result to related value (I simplified in your case within 1..10).

Upvotes: 4

Related Questions