Program to generate pick elements from array random following given weighted distribution

WeightedBiasRandomElementGenerator.java

package com.blogspot.yogidevendra.codesnippets;

import java.util.Arrays;
import java.util.Random;

/**
 * To generate Random numbers based on weighted bias.
 */

public class WeightedBiasRandomElementGenerator<T>
{
  private T[] items;
  private int[] weights;
  private int[] cumulativeWeights;
  private Random random;

  /**
   * @param items
   * @param weights
   */
  public WeightedBiasRandomElementGenerator(T[] items, int[] weights)
  {
    super();
    this.items = items;
    this.weights = weights;
  }

  /**
   * initialize cumulativeWeights
   */
  public void initialize()
  {
    random = new Random();
    
    int sumTillNow = 0;
    cumulativeWeights = new int[weights.length];
    for (int i = 0; i < weights.length; i++) {
      sumTillNow += weights[i];
      cumulativeWeights[i] = sumTillNow;
    }
  }

  /**
   * Generates random index honoring the given weights 
   * and returns corresponding item from the list.
   * @return
   */
  T getRandomElement()
  {
    // Generate random sample between 1 to sum(weights).
    // sum(weights) is available in cumulativeWeights[cumulativeWeights.length-1]
    int rand = random.nextInt(cumulativeWeights[cumulativeWeights.length-1]);
    int sample = rand + 1;
    //Find out index for which cumulativeWeight is less than or equal to sample
    int index = Arrays.binarySearch(cumulativeWeights, sample);
    //If exact match not found then binarysearch returns -(insertion point) -1
    //convert it to insertion point
    if (index < 0) {
      index = -(index+1);
    }
    return items[index];
  }

  /**
   * Demo run
   */
  public static void main(String[] args)
  {
    String[] fruits = { "Apple", "Banana", "Chikoo" };
    int[] weights = { 3, 1, 2 };
    WeightedBiasRandomElementGenerator<String> fruitsGenerator = new WeightedBiasRandomElementGenerator<String>(fruits, weights);
    fruitsGenerator.initialize();
    for(int i=0; i< 60000 ;i++){
      String fruit = fruitsGenerator.getRandomElement();
      System.out.println(fruit);
    }
  }
}

References: http://codetheory.in/weighted-biased-random-number-generation-with-javascript-based-on-probability/

Visit http://yogidevendra.blogspot.in/2014/11/weighted-bias-random-elements-generator.html for complete article on this

Not working with zero weights