时间戳

首页 > 解决方案 > 使用自定义分布生成序列

c++ - 使用自定义分布生成序列

问题描述

我有不同概率的n元素 向量。vector<elem> v;概率在范围内[0, 1]，它们的总和是1。

struct elem
{
   int value;
   double probability;
}

如何生成一个新的vector<elem>，其中每个elem都是根据该分布以概率选择的？如果我可以选择新向量的长度会更好。

标签： c++algorithmdistribution

解决方案

如果你想elem从向量v中选择一个概率与成员值成正比的，你需要实现一个选择方案，称为适应度成比例或轮盘赌选择。

要实现这一点，您可以首先根据数据成员的值创建一个“轮盘赌”：

std::vector<double> wheel, probs;

// extract the probabilities
std::transform(std::begin(v), std::end(v),
               std::back_inserter(probs),
               [](auto const & e) { return e.probability ; });

// then create the roulette wheel
std::partial_sum(std::begin(probs), std::end(probs),
                 std::back_inserter(wheel));

现在要做出一个选择，您可以旋转wheel，然后查看它落在轮子的哪个索引上。给定 的构造，登陆任何指数的概率与中相同指数的值wheel成正比。probabilityelemv

// create the random spinner, and uniformly distributed tip
std::mt19937 spinner;
std::uniform_real_distribution<double> tip(0., 1.); // since the sum is 1.
                                                    // In general, the second argument can be wheel.back()

// spin the wheel and selects an elem
auto spin = [&] {
   auto choice = std::lower_bound(std::begin(wheel), std::end(wheel), 
                                  tip(spinner));
   return v[std::distance(std::begin(wheel), choice)];
};

现在你可以生成一个你想要的任何大小的新向量。

// spin the wheel N times to generate next population
std::vector<elem> new_v;
std::generate_n(std::back_inserter(new_v), N, spin);

请注意，如果您想生成一个不重复元素的新向量，则必须付出更多努力以确保选择仍然是随机分布的。此选择还会受到您要生成的新向量大小的影响。

推荐阅读