加权随机数:边界情况

Question

参考这篇文章中给出的顶部答案，我注意到它在rnd=sum_of_weight的边界情况下失败。修复是在[0,sum_of_weight)中生成随机数，但我想知道为什么代码失败了这个边界情况?是算法的缺陷吗?

编辑:另外，权重数组需要从高到低排序吗?根据减法循环，似乎是这样的。

下面是实现上述伪代码的Java代码。

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 static void main(String[] args) {
    SimpleWeight sw = new SimpleWeight();
    sw.init();
    for (int i=0; i < 10;i++) {
        System.out.println(sw.next());
    }
}

Answer 1

你链接到的算法的第二步:

2)在0到之间随机选择一个小于权重之和的数。

对我来说，这清楚而明确地表明，正确的方法是从[0,sum_of_weight)中选择一个数字。从不同的范围中选择一个数字(例如，包括sum_of_weight的任何范围)不是算法中的缺陷，它是该算法的实现的缺陷。

edit不，算法不需要对权重进行排序

Answer 2

对于那些觉得有用的人来说，这里是上面的另一个实现。如果你想做得更好，也要接受反馈。我还是个初学者。

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);
    }
}