加权随机数生成 [英] Weighted random number generation

问题描述

我想以一种精确的方式生成加权随机数.我可以用一个例子确切地解释一下:我的输入数组是[1、2、3]，它们的权重又是[1、2、3].在那种情况下，我希望看到1代表1次，2代表2次，3代表3.像3-> 2-> 3-> 1-> 3-> 2 ...

I would like to generate weighted random numbers in an exact manner. I can explain exact with an example: My input array is [1, 2, 3] and their weights are again [1, 2, 3]. In that case I expect to see 1 for 1 times, 2 for 2 times and 3 for 3. Like 3 -> 2 -> 3 -> 1 -> 3 -> 2...

我正在使用rand()实现随机数生成，以获取[0，sum_of_weights)之间的范围.对于上面的示例，sum_of_weights = 1 + 2 + 3 = 6.我在Internet上搜索了现有的解决方案，但是结果不是我想要的.有时我得到2次超过2次，但序列中没有1次.它仍然是加权的，但不能完全给出我等待的次数.

I am implementing random number generation with rand() to get a range between [0, sum_of_weights). sum_of_weights = 1 + 2 + 3 = 6 for the example above. I searched for existing solutions on the Internet, however the result is not what I want. Sometimes I got 2 more than 2 times and no 1 in the sequence. Its still weighted but not exactly give the number of times I waited for.

我不确定下面的代码有什么问题.我应该做错什么还是尝试完全不同?感谢您的回答.

I am not sure whats wrong with my code below. Should I do something wrong or I try totally different? Thanks for your answers.

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 */
}

我还尝试了一些不同的方法(下面的代码).它适用于我的情况，但是整数溢出和静态变量的广泛使用使它成为问题.

I also tried something different (the code is below). It worked for my case, but integer overflow and extensive use of static variables makes it problematic.

如果在输入NULL之前输入输入数组并继续使用它.有点类似于strtok()的用法.

If you enter an input array before give NULL and continue to work with it. A little bit similar to strtok() usage.

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

推荐答案

这是您想要的吗?

# 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]

编辑:糟糕，出于某种原因，我想用Python替换C标记.无论如何，我认为您想要的不是加权"随机数生成器，而是随机播放. 这应该有帮助.

Whoops, for some reason my mind replaced the C tag with the Python one. Regardless, I think what you want is not "weighted" random number generators, but a shuffle. This ought to help.

这篇关于加权随机数生成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！