加权随机数
我试图实现一个加权的随机数字。 我现在只是把我的头撞在墙上，无法弄清楚。
在我的项目（Hold'em hand-ranges，主观全面权益分析）中，我使用了Boost的随机函数。 所以，假设我想select一个1到3之间的随机数（所以1,2或3）。 Boost的mersenne扭曲发生器就像一个魅力。 不过，我希望这个select权重是这样的例子：
1 (weight: 90) 2 (weight: 56) 3 (weight: 4) Boost是否具有某种function？
有一个随机挑选项目的简单algorithm，其中项目具有单独的权重：
1）计算所有权重的总和
2）select一个0或更大的随机数，小于权重的总和
3）逐个检查一个项目，从你的随机数中减去它们的重量，直到你得到的项目的随机数小于该项目的重量
伪代码说明这一点：
int sum_of_weight = 0; for(int i=0; i<num_choices; i++) { sum_of_weight += choice_weight[i]; } int rnd = random(sum_of_weight); for(int i=0; i<num_choices; i++) { if(rnd < choice_weight[i]) return i; rnd -= choice_weight[i]; } assert(!"should never get here");
这应该是简单的适应你的提升容器等。
如果你的权重很less被改变，但是你经常随机select一个，只要你的容器存储的是指向对象的指针，或者超过几十个项目（基本上，你必须知道这是否有帮助或妨碍） ，那么有一个优化：
通过在每个项目中存储累计重量总和，您可以使用二进制search来select与拾取重量相对应的项目。
如果你不知道列表中的项目数量，那么有一个非常整洁的algorithm，称为油藏采样 ，可以加以调整。
更新了对旧问题的回答。 你可以很容易地在C ++ 11中用std :: lib来做到这一点：
#include <iostream> #include <random> #include <iterator> #include <ctime> #include <type_traits> #include <cassert> int main() { // Set up distribution double interval[] = {1, 2, 3, 4}; double weights[] = { .90, .56, .04}; std::piecewise_constant_distribution<> dist(std::begin(interval), std::end(interval), std::begin(weights)); // Choose generator std::mt19937 gen(std::time(0)); // seed as wanted // Demonstrate with N randomly generated numbers const unsigned N = 1000000; // Collect number of times each random number is generated double avg[std::extent<decltype(weights)>::value] = {0}; for (unsigned i = 0; i < N; ++i) { // Generate random number using gen, distributed according to dist unsigned r = static_cast<unsigned>(dist(gen)); // Sanity check assert(interval[0] <= r && r <= *(std::end(interval)-2)); // Save r for statistical test of distribution avg[r - 1]++; } // Compute averages for distribution for (double* i = std::begin(avg); i < std::end(avg); ++i) *i /= N; // Display distribution for (unsigned i = 1; i <= std::extent<decltype(avg)>::value; ++i) std::cout << "avg[" << i << "] = " << avg[i-1] << '\n'; }
我的系统输出：
avg[1] = 0.600115 avg[2] = 0.373341 avg[3] = 0.026544
请注意，上面的大部分代码都是专门用来显示和分析输出的。 实际的一代只是几行代码。 输出结果表明所要求的“可能性”已经被获得。 你必须把请求的输出除以1.5，因为这是请求的总和。
当我需要权重时，我所做的是使用一个随机数字作为权重。
例如：我需要用下面的权重从1到3生成随机数：
- 随机数的10％可以是1
- 随机数的30％可以是2
- 随机数的60％可以是3
然后我使用：
weight = rand() % 10; switch( weight ) { case 0: randomNumber = 1; break; case 1: case 2: case 3: randomNumber = 2; break; case 4: case 5: case 6: case 7: case 8: case 9: randomNumber = 3; break; }
随机，它有10％的概率是1，30％是2和60％是3。
你可以根据你的需要玩它。
希望我能帮助你，祝你好运！
如果你的权重变化比绘制得慢，C ++ 11 discrete_distribution将是最简单的：
#include <random> #include <vector> std::vector<double> weights{90,56,4}; std::discrete_distribution<int> dist(std::begin(weights), std::end(weights)); std::mt19937 gen; gen.seed(time(0));//if you want different results from different runs int N = 100000; std::vector<int> samples(N); for(auto & i: samples) i = dist(gen); //do something with your samples...
但是请注意，c ++ 11 discrete_distribution计算初始化的所有累积和。 通常情况下，你需要这样做，因为它加快了一次O（N）成本的采样时间。 但是，对于快速变化的分配，将会产生沉重的计算（和记忆）成本。 例如，如果权重表示有多less个项目，并且每次绘制一个项目，都将其删除，您可能需要一个自定义algorithm。
Will的回答https://stackoverflow.com/a/1761646/837451避免了这个开销，但是比C ++ 11更慢，因为它不能使用二进制search。
要看到这一点，你可以看到相关的行（我的Ubuntu 16.04 + GCC 5.3安装/usr/include/c++/5/bits/random.tcc ）：
template<typename _IntType> void discrete_distribution<_IntType>::param_type:: _M_initialize() { if (_M_prob.size() < 2) { _M_prob.clear(); return; } const double __sum = std::accumulate(_M_prob.begin(), _M_prob.end(), 0.0); // Now normalize the probabilites. __detail::__normalize(_M_prob.begin(), _M_prob.end(), _M_prob.begin(), __sum); // Accumulate partial sums. _M_cp.reserve(_M_prob.size()); std::partial_sum(_M_prob.begin(), _M_prob.end(), std::back_inserter(_M_cp)); // Make sure the last cumulative probability is one. _M_cp[_M_cp.size() - 1] = 1.0; }
build立一个包（或std ::向量）的所有可以挑选的项目。
确保每个项目的数量与您的权重成正比。
例：
- 1 60％
- 2 35％
- 3 5％
所以有一个袋子有60个1，35 2和5 3个100个项目。
现在随机sorting包（std :: random_shuffle）
从包里依次挑选元素，直到它为空。
一旦空，重新随机化袋子，然后重新开始。
在[0,1）上select一个随机数，这个数字应该是升压RNG的默认运算符（）。 select累积概率密度函数> =该数字的项目：
template <class It,class P> It choose_p(It begin,It end,P const& p) { if (begin==end) return end; double sum=0.; for (It i=begin;i!=end;++i) sum+=p(*i); double choice=sum*random01(); for (It i=begin;;) { choice -= p(*i); It r=i; ++i; if (choice<0 || i==end) return r; } return begin; //unreachable }
其中random01（）返回一个double> = 0和<1。 请注意，上述不要求概率总和为1; 它为你规范化他们。
p只是为集合中的项目分配概率的函数[开始，结束]。 如果你只是有一个概率序列，你可以忽略它（或使用一个标识）。
我已经实现了几个简单的加权随机algorithm 。
