c++ - 加权随机n次优化

Question

一个数组中有10个加权元素。我想在一个随机的N时间选择一个元素，然后计算每个元素出现的次数。是否有一种算法可以为我提供元素计数，而无需选择N时间？ N可能数量很多，在这种情况下，必须生成N样本效率很低。

例如:
一个盒子里有2个红球和8个白球。从盒子里随机挑一个球，然后放回去，重复100次。计算红球或白球被拣选的总次数。

我想知道是否有可能在不进行100次采样的情况下获得计数。

Answer 1

假设数组有n个元素。令X1，X2，...，Xn表示随机变量，其中Xi表示第n个元素出现的次数，然后以X1 = x1，X2 = x2，...，和X(i-1)= x为条件(i-1)，Xi遵守参数(N-x1-x2-...-x(i-1))和1 /(n-i + 1)的binomial distribution。因此您可以按如下顺序绘制X1，X2，...，Xn:

#include <iostream>
#include <random>

template <typename Iter, typename Int_type>
void draw(Iter begin, Iter end, Int_type N)
{
    auto n = std::distance(begin, end);
    static std::mt19937 gen{std::random_device{}()};
    while (begin != end) {
        std::binomial_distribution<Int_type> d(N, 1 / static_cast<double>(n));
        auto number = d(gen);
        *begin++ = number;
        --n;
        N -= number;
    }
}

int main()
{
    unsigned count[10];
    draw(std::begin(count), std::end(count), 10000u);
    for (auto i : count) std::cout << i << ", ";
}