Weighted Randomness in Java

Weighted randomness in Java

2020 Update (interesting how this got 37 upvotes with a glaring bug in the 2011 version below):

• Fix the impossibility to select the last item when Math.random() yields a number very close to 1.0, and we are unlucky with floating point precision: random index -1 would be the result, which is obviously wrong.
• Some code compaction
• Less variable names used

Item[] items = ...;

// Compute the total weight of all items together.
// This can be skipped of course if sum is already 1.
double totalWeight = 0.0;
for (Item i : items) {
    totalWeight += i.getWeight();
}

// Now choose a random item.
int idx = 0;
for (double r = Math.random() * totalWeight; idx < items.length - 1; ++idx) {
    r -= items[idx].getWeight();
    if (r <= 0.0) break;
}
Item myRandomItem = items[idx];

---

2011 version (for comparison left in):

Item[] items = ...;

// Compute the total weight of all items together
double totalWeight = 0.0d;
for (Item i : items)
{
    totalWeight += i.getWeight();
}
// Now choose a random item
int randomIndex = -1;
double random = Math.random() * totalWeight;
for (int i = 0; i < items.length; ++i)
{
    random -= items[i].getWeight();
    if (random <= 0.0d)
    {
        randomIndex = i;
        break;
    }
}
Item myRandomItem = items[randomIndex];

---

Simulating weighted random number - Java

A simple approach could be as follows. No need to *2, because probabilities will be the same.

    String giantRat []={"Bandage", "Healing Potion", "Minor Healing Potion", "Rat Teeth", "Fur", "Rat Tail", ""};

    int[] a = {1,1,1,6,8,3,5};
    int sum = 0;
    for(int i: a)
       sum += i;
    Random r = new Random();
    int s = r.nextInt(sum);  //Get selection position (not array index)

    //Find position in the array:
    int prev_value = 0;
    int current_max_value = 0;
    int found_index = -1;
    for(int i=0; i< a.length; i++){ //walk through the array
      current_max_value = prev_value + a[i];
      //is between beginning and end of this array index?
      boolean found = (s >= prev_value && s < current_max_value)? true : false;
      if( found ){
        found_index = i;
        break;
      }
      prev_value = current_max_value;
    }

    String selection = "unknown";
    if( found_index != -1 ){
      selection = giantRat[found_index];
    }
    System.out.println(selection);

Example at http://ideone.com/xyQlvN

Weighted-random probability in Java

If you want to select "one of these Doubles, with an extreme likelihood of it being the first one, then decreasing likelihood for each item, until the final one is close to 0% chance of it being the final item in the list" then it seems like you want an exponential probability function. (p = x²).

However, you will only know whether you have chosen the right function once you have coded a solution and tried it, and if it does not suit your needs then you will need to choose some other probability function, like a sinusoidal (p = sin( x * PI/2 )) or an inverse ratio (p = 1/x).

So, the important thing is to code an algorithm for selecting an item based on a probability function, so that you can then try any probability function you like.

So, here is one way to do it.

Note the following:

1. I am seeding the random number generator with 10 in order to always produce the same results. Remove the seeding to get different results at each run.

2. I am using a list of Integer for your "percentages" in order to avoid confusion. Feel free to replace with a list of Double once you have understood how things work.

3. I am providing a few sample probability functions. Try them to see what distributions they yield.

Have fun!

import java.util.*;

public final class Scratch3
{
    private Scratch3()
    {
    }

    interface ProbabilityFunction<T>
    {
        double getProbability( double x );
    }

    private static double exponential2( double x )
    {
        assert x >= 0.0 && x <= 1.0;
        return StrictMath.pow( x, 2 );
    }

    private static double exponential3( double x )
    {
        assert x >= 0.0 && x <= 1.0;
        return StrictMath.pow( x, 3 );
    }

    private static double inverse( double x )
    {
        assert x >= 0.0 && x <= 1.0;
        return 1/x;
    }

    private static double identity( double x )
    {
        assert x >= 0.0 && x <= 1.0;
        return x;
    }

    @SuppressWarnings( { "UnsecureRandomNumberGeneration", "ConstantNamingConvention" } )
    private static final Random randomNumberGenerator = new Random( 10 );

    private static <T> T select( List<T> values, ProbabilityFunction<T> probabilityFunction )
    {
        double x = randomNumberGenerator.nextDouble();
        double p = probabilityFunction.getProbability( x );
        int i = (int)( p * values.size() );
        return values.get( i );
    }

    public static void main( String[] args )
    {
        List<Integer> values = Arrays.asList( 10, 11, 12, 13, 14, 15 );
        Map<Integer,Integer> counts = new HashMap<>();
        for( int i = 0;  i < 10000;  i++ )
        {
            int value = select( values, Scratch3::exponential3 );
            counts.merge( value, 1, ( a, b ) -> a + b );
        }
        for( int value : values )
            System.out.println( value + ": " + counts.get( value ) );
    }
}

Weighted Randomized Ordering

This seems to work fine:

// Can do a weighted sort on weighted items.
public interface Weighted {
    int getWeight();
}

/**
 * Weighted sort of an array - orders them at random but the weight of each
 * item makes it more likely to be earlier.
 *
 * @param values
 */
public static void weightedSort(Weighted[] values) {
    // Build a list containing as many of each item to make up the full weight.
    List<Weighted> full = new ArrayList<>();
    for (Weighted v : values) {
        // Add a v weight times.
        for (int i = 0; i < v.getWeight(); i++) {
            full.add(v);
        }
    }
    // Shuffle it.
    Collections.shuffle(full);
    // Roll them out in the order required.
    int i = 0;
    do {
        // Get the first one in the shuffled list.
        Weighted next = full.get(0);
        // Put it back into the array.
        values[i++] = next;
        // Remove all occurrences of that one from the list.
        full.remove(next);
    } while (!full.isEmpty());
}

// A bunch of weighted items.
enum Heavies implements Weighted {

    Rare(1),
    Few(3),
    Common(6);
    final int weight;

    Heavies(int weight) {
        this.weight = weight;
    }

    @Override
    public int getWeight() {
        return weight;
    }
}

public void test() {
    Weighted[] w = Heavies.values();
    for (int i = 0; i < 10; i++) {
        // Sort it weighted.
        weightedSort(w);
        // What did we get.
        System.out.println(Arrays.toString(w));
    }
}

Essentially for each item to be sorted I add it as many times as needed to a new list. I then shuffle the list and pull the top one out and clar all occurrences of it from the remaining.

The last test run produced:

[Rare, Common, Few]
[Common, Rare, Few]
[Few, Common, Rare]
[Common, Few, Rare]
[Common, Rare, Few]
[Few, Rare, Common]

which seems to be about right.

NB - this algorithm will fail under at least the following conditions:

1. The original array has the same object in it more than once.
2. The weights of the items are insanely huge.
3. Zero or negative weights will almost certainly mess with the results.

Added

This implements Rossum's idea - please be sure to give him the credit for the algorithm.

public static void weightedSort2(Weighted[] values) {
    // Calculate the total weight.
    int total = 0;
    for (Weighted v : values) {
        total += v.getWeight();
    }
    // Start with all of them.
    List<Weighted> remaining = new ArrayList(Arrays.asList(values));
    // Take each at random - weighted by it's weight.
    int which = 0;
    do {
        // Pick a random point.
        int random = (int) (Math.random() * total);
        // Pick one from the list.
        Weighted picked = null;
        int pos = 0;
        for (Weighted v : remaining) {
            // Pick this ne?
            if (pos + v.getWeight() > random) {
                picked = v;
                break;
            }
            // Move forward by that much.
            pos += v.getWeight();
        }
        // Removed picked from the remaining.
        remaining.remove(picked);
        // Reduce total.
        total -= picked.getWeight();
        // Record picked.
        values[which++] = picked;
    } while (!remaining.isEmpty());
}

JAVA - How do I generate a random number that is weighted towards certain numbers?

public static void main(String[] args){
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.add(5);list.add(2);// to be continued ...        
    int randomInt = list.get((int) (Math.random() * list.size()));
    System.out.println(randomInt);
}

You'll get your List of values, and then you just need to pick randomly an index and get back the value

Math.random() will pick a value in [0;1[, if you multiply by the size of a List of 10 elements, you'll a value in [0;10[ , when you cast as an int you'll get 10 possibilities of index to look into the List

The ArrayList (implementation of List) allows duplicate element so :
if you add 1,2,2,3,4,5,6,7,8,9 (the order does not matter) you'll have 10 elements with each one to be find with 1/10 = 10/100 = 10% of probability (aka chance), but the element 2 which appears twice will have 20% chance to be choosen in the method, more the number appears more it's chance to be choosen increase, with as you said (number of time the number appears)/(total number of element) (this is basic maths)

How to choose a random number in a weighted way

Accumulate the values in list and call the resulting sum S. Now generate a random number from 0 to S - 1. Iterate once more over list and for each element do the following: if the element is greater then S than choose that element. Otherwise decrease S by the element's value and continue on to the next element.

Choosing random value from weighted options in java

If you want to keep it simple, you could do the following:

int random = Math.random();

if (random < 0.05) { // 5/100
  return "Platinum";
} else if (random < 0.1) { // 10/100
  return "Gold";
} else if (random < 0.2) { // 20/100
  return "Silver";
} else if (random < 0.3) { // 30/100
  return "Bronze";
} else {
  return "You didn't get anything.";
} 

---

Related Topics