Взвешенные случайные числа: граничный случай - PullRequest
Новая
       0

Взвешенные случайные числа: граничный случай

4 голосов
/ 14 сентября 2011

Что касается верхнего ответа, данного в этом посте , я заметил, что он не работает для граничного случая, когда 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());
    }
}

Ответы [ 2 ]

3 голосов
/ 14 сентября 2011

Шаг 2 алгоритма вы ссылаетесь на состояния:

2) выберите случайное число от 0 до меньше, чем сумма весов.

Для меня это ясно и недвусмысленно говорит о том, что правильный путь - это выбрать число из [0,sum_of_weight). Выбор числа из другого диапазона (например, любого диапазона, включающего sum_of_weight) не является недостатком алгоритма, это недостаток реализации этого алгоритма.

edit Нет, для работы алгоритма веса не нужно сортировать.

0 голосов
/ 25 мая 2012

Для тех, кто считает это полезным, вот еще одна реализация вышеупомянутого.Открыто для обратной связи, если вы хотите улучшить его.Я еще новичок. 

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

}
...