Wsrtjtyk

Some time ago I wrote a helper class to solve this issue. The source code should show the concept clear enough:

public class DistributedRandomNumberGenerator {



    private Map<Integer, Double> distribution;

    private double distSum;



    public DistributedRandomNumberGenerator() {

        distribution = new HashMap<>();

    }



    public void addNumber(int value, double distribution) {

        if (this.distribution.get(value) != null) {

            distSum -= this.distribution.get(value);

        }

        this.distribution.put(value, distribution);

        distSum += distribution;

    }



    public int getDistributedRandomNumber() {

        double rand = Math.random();

        double ratio = 1.0f / distSum;

        double tempDist = 0;

        for (Integer i : distribution.keySet()) {

            tempDist += distribution.get(i);

            if (rand / ratio <= tempDist) {

                return i;

            }

        }

        return 0;

    }



}

The usage of the class is as follows:

DistributedRandomNumberGenerator drng = new DistributedRandomNumberGenerator();

drng.addNumber(1, 0.3d); // Adds the numerical value 1 with a probability of 0.3 (30%)

// [...] Add more values



int random = drng.getDistributedRandomNumber(); // Generate a random number

Test driver to verify functionality:

    public static void main(String args) {

        DistributedRandomNumberGenerator drng = new DistributedRandomNumberGenerator();

        drng.addNumber(1, 0.2d);

        drng.addNumber(2, 0.3d);

        drng.addNumber(3, 0.5d);



        int testCount = 1000000;



        HashMap<Integer, Double> test = new HashMap<>();



        for (int i = 0; i < testCount; i++) {

            int random = drng.getDistributedRandomNumber();

            test.put(random, (test.get(random) == null) ? (1d / testCount) : test.get(random) + 1d / testCount);

        }



        System.out.println(test.toString());

    }

Sample output for this test driver:

{1=0.20019100000017953, 2=0.2999349999988933, 3=0.4998739999935438}

You already wrote the implementation in your question. ;)

final int ran = myRandom.nextInt(100);

if (ran > 50) { return 3; }

else if (ran > 20) { return 2; } 

else { return 1; }

You can speed this up for more complex implementations by per-calculating the result on a switch table like this:

t[0] = 1; t[1] = 1; // ... one for each possible result

return t[ran];

But this should only be used if this is a performance bottleneck and called several hundred times per second.

If you have performance issue instead of searching all the n values O(n)

you could perform binary search which costs O(log n)

Random r=new Random();      

double weights=new double{0.1,0.1+0.2,0.1+0.2+0.5};

// end of init

double random=r.nextDouble();

// next perform the binary search in weights array

you only need to access log2(weights.length) in average if you have a lot of weights elements.

Your approach is fine for the specific numbers you picked, although you could reduce storage by using an array of 10 instead of an array of 100. However, this approach doesn't generalize well to large numbers of outcomes or outcomes with probabilities such as 1/e or 1/PI.

A potentially better solution is to use an alias table. The alias method takes O(n) work to set up the table for n outcomes, but then is constant time to generate regardless of how many outcomes there are.

Try this:
In this example i use an array of chars, but you can substitute it with your integer array.

Weight list contains for each char the associated probability.
It represent the probability distribution of my charset.

In weightsum list for each char i stored his actual probability plus the sum of any antecedent probability.

For example in weightsum the third element corresponding to 'C', is 65:

P('A') + P('B) + P('C') = P(X=>c)

10 + 20 + 25 = 65

So weightsum represent the cumulative distribution of my charset.
weightsum contains the following values:

It's easy to see that the 8th element correspondig to H, have a larger gap (80 of course like his probability) then is more like to happen!

        List<Character> charset =   Arrays.asList('A','B','C','D','E','F','G','H','I','J');

        List<Integer> weight = Arrays.asList(10,30,25,60,20,70,10,80,20,30);

        List<Integer>  weightsum = new ArrayList<>();



        int i=0,j=0,k=0;

        Random Rnd = new Random();



        weightsum.add(weight.get(0));



        for (i = 1; i < 10; i++)

            weightsum.add(weightsum.get(i-1) + weight.get(i));

Then i use a cycle to get 30 random char extractions from charset,each one drawned accordingly to the cumulative probability.

In k i stored a random number from 0 to the max value allocated in weightsum.
Then i look up in weightsum for a number grather than k, the position of the number in weightsum correspond to the same position of the char in charset.

   for (j = 0; j < 30; j++)

   {

   Random r = new Random();

   k =   r.nextInt(weightsum.get(weightsum.size()-1));



   for (i = 0; k > weightsum.get(i); i++) ;

   System.out.print(charset.get(i));

   }

The code give out that sequence of char:

HHFAIIDFBDDDHFICJHACCDFJBGBHHB

Let's do the math!

A = 2

B = 4

C = 3

D = 5

E = 0

F = 4

G = 1

H = 6

I = 3

J = 2

Total.:30

As we wish D and H are have more occurances (70% and 80% prob.)

Otherwinse E didn't come out at all. (10% prob.)

Written this class for interview after referencing the paper pointed by pjs in another post , the population of base64 table can be further optimized. The result is amazingly fast, initialization is slightly expensive, but if the probabilities are not changing often, this is a good approach.

*For duplicate key, the last probability is taken instead of being combined (slightly different from EnumeratedIntegerDistribution behaviour)

public class RandomGen5 extends BaseRandomGen {



    private int t_array = new int[4];

    private int sumOfNumerator;

    private final static int DENOM = (int) Math.pow(2, 24);

    private static final int bitCount = new int {18, 12, 6, 0};

    private static final int cumPow64 = new int {

            (int) ( Math.pow( 64, 3 ) + Math.pow( 64, 2 ) + Math.pow( 64, 1 ) + Math.pow( 64, 0 ) ),

            (int) ( Math.pow( 64, 2 ) + Math.pow( 64, 1 ) + Math.pow( 64, 0 ) ),

            (int) ( Math.pow( 64, 1 ) + Math.pow( 64, 0 ) ),

            (int) ( Math.pow( 64, 0 ) )

    };





    ArrayList base64Table = {new ArrayList<Integer>()

            , new ArrayList<Integer>()

            , new ArrayList<Integer>()

            , new ArrayList<Integer>()};



    public int nextNum() {

        int rand = (int) (randGen.nextFloat() * sumOfNumerator);



        for ( int x = 0 ; x < 4 ; x ++ ) {

                if (rand < t_array[x])

                    return x == 0 ? (int) base64Table[x].get(rand >> bitCount[x])

                            : (int) base64Table[x].get( ( rand - t_array[x-1] ) >> bitCount[x]) ;

        }

        return 0;

    }



    public void setIntProbList( int intList, float probList ) {

        Map<Integer, Float> map = normalizeMap( intList, probList );

        populateBase64Table( map );

    }



    private void clearBase64Table() {

        for ( int x = 0 ; x < 4 ; x++ ) {

            base64Table[x].clear();

        }

    }



    private void populateBase64Table( Map<Integer, Float> intProbMap ) {

        int startPow, decodedFreq, table_index;

        float rem;



        clearBase64Table();



        for ( Map.Entry<Integer, Float> numObj : intProbMap.entrySet() ) {

            rem = numObj.getValue();

            table_index = 3;

            for ( int x = 0 ; x < 4 ; x++ ) {

                decodedFreq = (int) (rem % 64);

                rem /= 64;

                for ( int y = 0 ; y < decodedFreq ; y ++ ) {

                    base64Table[table_index].add( numObj.getKey() );

                }

                table_index--;

            }

        }



        startPow = 3;

        for ( int x = 0 ; x < 4 ; x++ ) {

            t_array[x] = x == 0 ? (int) ( Math.pow( 64, startPow-- ) * base64Table[x].size() )

                    : ( (int) ( ( Math.pow( 64, startPow-- ) * base64Table[x].size() ) + t_array[x-1] ) );

        }



    }



    private Map<Integer, Float> normalizeMap( int intList, float probList ) {

        Map<Integer, Float> tmpMap = new HashMap<>();

        Float mappedFloat;

        int numerator;

        float normalizedProb, distSum = 0;



        //Remove duplicates, and calculate the sum of non-repeated keys

        for ( int x = 0 ; x < probList.length ; x++ ) {

            mappedFloat = tmpMap.get( intList[x] );

            if ( mappedFloat != null ) {

                distSum -= mappedFloat;

            } else {

                distSum += probList[x];

            }

            tmpMap.put( intList[x], probList[x] );

        }



        //Normalise the map to key -> corresponding numerator by multiplying with 2^24

        sumOfNumerator = 0;

        for ( Map.Entry<Integer, Float> intProb : tmpMap.entrySet() ) {

            normalizedProb = intProb.getValue() / distSum;

            numerator = (int) ( normalizedProb * DENOM );

            intProb.setValue( (float) numerator );

            sumOfNumerator += numerator;

        }



        return tmpMap;

    }

}

If you are not against adding a new library in your code, this feature is already implemented in MockNeat, check the probabilities() method.

Some examples directly from the wiki:

String s = mockNeat.probabilites(String.class)

                .add(0.1, "A") // 10% chance

                .add(0.2, "B") // 20% chance

                .add(0.5, "C") // 50% chance

                .add(0.2, "D") // 20% chance

                .val();

Or if you want to generate numbers within given ranges with a given probability you can do something like:

Integer x = m.probabilites(Integer.class)

             .add(0.2, m.ints().range(0, 100))

             .add(0.5, m.ints().range(100, 200))

             .add(0.3, m.ints().range(200, 300))

             .val();

Disclaimer: I am the author of the library, so I might be biased when I am recommending it.

Here is the python code even though you ask for java, but it's very similar.

# weighted probability



theta = np.array([0.1,0.25,0.6,0.05])

print(theta)



sample_axis = np.hstack((np.zeros(1), np.cumsum(theta))) 

print(sample_axis)

[0. 0.1 0.35 0.95 1. ]. This represent the cumulative distribution.

you can use a uniform distribution to draw an index in this unit range.

def binary_search(axis, q, s, e):

    if e-s <= 1:

        print(s)

        return s

    else: 

        m = int( np.around( (s+e)/2 ) )

        if q < axis[m]:

            binary_search(axis, q, s, m)

        else:

            binary_search(axis, q, m, e)







range_index = np.random.rand(1)

print(range_index)

q = range_index

s = 0

e = sample_axis.shape[0]-1

binary_search(sample_axis, q, 0, e)

Also responded here: find random country but probability of picking higher population country should be higher. Using TreeMap:

TreeMap<Integer, Integer> map = new TreeMap<>();

map.put(percent1, 1);

map.put(percent1 + percent2, 2);

// ...



int random = (new Random()).nextInt(100);

int result = map.ceilingEntry(random).getValue();