Генерация взвешенного случайного числа

Question

Я хотел бы генерировать взвешенные случайные числа точным способом.Я могу объяснить точное с помощью примера: мой входной массив [1, 2, 3] и их веса снова [1, 2, 3].В этом случае я ожидаю увидеть 1 для 1 раз, 2 для 2 раза и 3 для 3. Как 3 -> 2 -> 3 -> 1 -> 3 -> 2 ...

Я реализуюгенерация случайных чисел с помощью rand () для получения диапазона между [0, sum_of_weights).sum_of_weights = 1 + 2 + 3 = 6 для примера выше.Я искал существующие решения в Интернете, но результат не тот, который я хочу.Иногда я получил 2 более 2 раз и не 1 в последовательности.Он все еще взвешен, но не точно показывает количество раз, которое я ждал.

Я не уверен, что не так с моим кодом ниже.Должен ли я сделать что-то не так или я стараюсь совершенно иначе?Спасибо за ваши ответы.

int random_t (int items[], int items_weight[], int number_of_items)  
{   
    double random_weight;  
    double sum_of_weight = 0;
    int i;

    /* Calculate the sum of weights */  
    for (i = 0; i < number_of_items; i++) {
        sum_of_weight += items_weight[i];
    }

    /* Choose a random number in the range [0,1) */
    srand(time(NULL));
    double g = rand() / ( (double) RAND_MAX + 1.0 );
    random_weight = g * sum_of_weight;

    /* Find a random number wrt its weight */
    int temp_total = 0;

    for (i = 0; i < number_of_items; i++) 
    {
            temp_total += items_weight[i];

            if (random_weight < temp_total)
            {
                return items[i];
            } 
    }   
        return -1; /* Oops, we could not find a random number */
}

Я также попробовал что-то другое (код ниже).В моем случае это сработало, но целочисленное переполнение и широкое использование статических переменных делает его проблематичным.

Если вы вводите входной массив перед тем, как задать NULL и продолжить работу с ним.Немного похоже на использование strtok ().

int random_w(int *arr, int weights[], int size)
{
    int selected, i;
    int totalWeight;
    double ratio;
    static long int total;
    static long int *eachTotal = NULL;
    static int *local_arr = NULL;
    static double *weight = NULL;

    if (arr != NULL) 
        {
            free(eachTotal);
            free(weight);
            eachTotal = (long int*) calloc(size, sizeof(long));
            weight = (double*) calloc(size, sizeof(double));
            total = 0;
            totalWeight = 0;
            local_arr = arr;

            for (i = 0; i < size; i++) 
            {
                totalWeight += weights[i];
            }

            for (i = 0; i < size; i++)
            {
                weight[i] = (double)weights[i] / totalWeight;
            }
            srand(time(NULL));
        }

    while (1)
    {
        selected = rand() % size;
        ratio = (double)(eachTotal[selected])/(double)(total+1);
        if (ratio < weight[selected])
        {
            total++;
            eachTotal[selected]++;

            return local_arr[selected];
        }
    }
}

Answer 1

Это то, что вы хотите?

# Weights: one 1, two 2s, three 3s
>>> import random
>>> vals = [1] * 1 + [2] * 2 + [3] * 3
>>> random.shuffle(vals)
>>> vals
[2, 3, 1, 2, 3, 3]

Редактировать: Упс, почему-то мой разум заменил тег C на Python. В любом случае, я думаю, что вам нужны не «взвешенные» генераторы случайных чисел, а случайное перемешивание. Это должно помочь.

Answer 2

Вы можете произвести выборку из полиномиального распределения . Ваша вселенная случайных выборок (или «урна шаров в ведре») равна {1, 2, 3}, а вероятности («веса») наблюдения каждой из них соответственно {1/6, 2/6, 3/6}.

В демонстрационных целях скрипт Perl может дать вам список наблюдений помеченных шаров с такими вероятностями:

#!/usr/bin/perl

use strict;
use warnings;
use Math::Random qw(random_multinomial);
use Data::Dumper;

my $events = 10;
my @probabilities = qw(0.167 0.333 0.5);
my @observations = random_multinomial($events, @probabilities);

print Dumper \@observations;

Для 10 событий одно испытание вернет что-то вроде:

$VAR1 = 1;
$VAR2 = 2;
$VAR3 = 7;

Это означает, что у вас есть (из этого единственного испытания) одно 1 -меченное событие, два 2 -меченных события и семь 3 -меченных событий.

Если вы повторите пробную версию, вы можете получить другое распределение событий, помеченных 1, 2 и 3.

Из этого списка можно составить тривиальный список {1, 2, 2, 3, 3, 3, 3, 3, 3, 3}.

Просто случайным образом перемешайте второй список, чтобы получить взвешенный наблюдаемый список случайных чисел.

Answer 3

Когда вы говорите, что не получили «точно» ожидаемое количество значений для каждого взвешенного значения, сколько прогонов вы говорите? Если бы вы только выполнили шесть прогонов любого случайного процесса, я бы не ожидал, что вы сможете окончательно сказать, что сработало или нет. Ваш код может работать нормально. Попробуйте запустить его миллион раз и проверьте результаты. Или, может быть, вы на самом деле хотите, о чем говорит Натон, предварительно взвешенный список значений, который вы можете затем произвольно перемешать и по-прежнему иметь точные веса, которые ищете.

Answer 4

хорошо, мой ответ будет звучать как хак - но коротко или писать свой собственный дистрибутив - может быть, вы можете сопоставить единообразное распределение и увеличить рычаг (посмотрите http://www.boost.org/doc/libs/1_44_0/doc/html/boost_random/reference.html#boost_random.reference.distributions)

, так что следуйте вашему примеру:

• 1 -> 1
• 2,3 -> 2
• 4,5,6 -> 3
• 7,8,9,10-> 4 (и т. Д.)

, затем сгенерируйте случайное число от 1 до 10 и верните отображенный элемент. Затем используйте распределение boost_iform_int для получения числа, которое вы затем отобразите.

Вот пример генерации чисел, вам нужно будет отобразить результаты:

#include <iostream>
#include <boost/random.hpp>
#include <time.h>
using namespace std;
using namespace boost;

int main ( )  {

    uniform_int<> distribution(0, 10) ;
    mt19937 engine; 
    engine.seed(time(NULL));   
    variate_generator<mt19937, uniform_int<> > myrandom (engine, distribution);

    cout << myrandom() << endl;

}

Answer 5

Если вы хотите, чтобы сэмплированные частоты были полностью детерминированными, я думаю, что лучше всего сгенерировать массив, который имеет правильное количество вхождений для каждого значения, затем выполнить случайное перемешивание (которое сохраняет частоты) и принять последовательныеэлементы перемешанного массива в качестве вашей случайной последовательности.