Weighted random numbers: boundary case

In reference to the top answer given in this post, I've noticed that it fails for a boundary case when rnd=sum_of_weight. The fix is to generate random numbers in [0,sum_of_weight), however i was wondering why the code fails for this boundary case? Is it a flaw in the algorithm?

EDIT: Also, does the weight array need to be sorted high to low? It seems so, based on the subtraction loop.

Below is the Java code that implements the pseudo-code in the above post.

int sum_of_weight = 0;



int []choice_weight = {50, 15, 15, 10, 10};         // percentages
int num_choices = choice_weight.length;

public void init() {

    for (int i = 0; i < num_choices; i++) {
        sum_of_weight += choice_weight[i];
    }
}

int next() {
    int rnd = (int)Util.between(0, sum_of_weight);// random(sum_of_weight);
    rnd=sum_of_weight;                      // force the exception by hitting boundary case
    //System.out.print("rnd=" + rnd);
    for (int i = 0; i < num_choices; i++) {
        if (rnd < choice_weight[i])
            return i;
        rnd -= choice_weight[i];
    }

    throw new RuntimeException("should never get here for rnd=" + rnd);
}

public s开发者_运维百科tatic void main(String[] args) {
    SimpleWeight sw = new SimpleWeight();
    sw.init();
    for (int i=0; i < 10;i++) {
        System.out.println(sw.next());
    }
}

Step 2 of the algorithm you link to states:

2) pick a random number between 0 and less than the sum weights.

To me, this reads clearly and unambiguously that the correct way is to pick a number from [0,sum_of_weight). Picking a number from a different range (e.g. any range that includes sum_of_weight) isn't a flaw in the algorithm, it's a flaw in the implementation of that algorithm.

edit No, the weights do not need to be sorted for the algorithm to work.

For those that find it useful, here is another implementation of the above. Open to feedback too if you want to make it better. I'm still a beginner.

import java.util.Random;

public class WeightedRandom {

    private int choiceWeight[];
    private int numChoices = 0;
    private int i = 0;
    private Random r = new Random();

    public WeightedRandom() {
        this.choiceWeight = new int[] { 60, 35, 5 };
        this.numChoices = choiceWeight.length;
    }

    public WeightedRandom(int[] choiceWeight) {
        this.choiceWeight = choiceWeight;
        this.numChoices = this.choiceWeight.length;
    }

    public int weightedRandomGenerator() {

        int sumOfWeight = 0;
        for (int i = 0; i < numChoices; i++) {
            sumOfWeight += choiceWeight[i];
        }

        int randomNumber = r.nextInt(sumOfWeight);
        for (int i = 0; i < numChoices; i++) {
            if (randomNumber < choiceWeight[i])
                return i;
            randomNumber -= choiceWeight[i];
        }

        throw new RuntimeException("should never get here for RandomNumber = " + randomNumber);
    }

    public void printWeightedAverage(int numberOfIterations) {
        int numberCount[] = new int[numChoices];

        for (int n = 0; n < numberOfIterations; n++) {
            i = weightedRandomGenerator();
            numberCount[i]++;
        }

        for (int n = 0; n < numChoices; n++)
            System.out.println("Occurance of " + n + " = " + (((double) numberCount[n]) / numberOfIterations) * 100 + "%");
        System.out.println("--------");
    }

    public static void main(String[] args) {

        WeightedRandom wr = new WeightedRandom();
        WeightedRandom wr2 = new WeightedRandom(new int[] { 49, 25, 15, 5, 3, 2, 1 });
        wr.printWeightedAverage(100_000_000);
        wr2.printWeightedAverage(100_000_000);
    }

}