c - 加权随机数生成

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]

编辑:哎呀，出于某种原因，我的想法用 Python 标签替换了 C 标签。无论如何，我认为你想要的不是“加权”随机数生成器，而是随机播放。 This应该有帮助。