C ++.加权std :: shuffle [英] C++. Weighted std::shuffle
问题描述
有没有一种方法可以使用标准库进行漂亮而优雅的加权改组?
有std::discrete_distribution
.
我想要的是这样的:
Is there a way to do nice and elegant weighted shuffling using standard library?
There is std::discrete_distribution
.
What I want is something like this:
std::vector<T> data { N elements };
std::vector<int> weights { N weights };
std::shuffle(std::begin(data), std::end(data), something based on discrete distribution);
推荐答案
如果OP意图是对项目列表 r 进行洗牌
If OP intent is to shuffle a list r of items
这样,在给定权重列表 w 的情况下,权重为 w [i] 的元素 a [i] 应该是第一个随机洗牌 r 的元素,概率为 w [i]/sum(w).
such that, given a list of weights w, the element a[i] with weight w[i] should be the first element of the random shuffle r with probability w[i]/sum(w).
由
As stated in the page linked by Severin Pappadeux:
加权随机混洗与列表a中的加权随机采样相同,没有替换.即,以概率w [i]/sum(w)从a中选择元素a [i].将此元素存储在列表r中.然后,从a中删除元素a [i],从w中删除w [i],并从修改后的列表a中选择一个新元素,依此类推,直到a为空.
Weighted random shuffling is the same as weighted random sampling from a list a without replacement. That is, choose with probability w[i]/sum(w) element a[i] from a. Store this element in a list r. Then, remove element a[i] from a and w[i] from w, and select a new element of the modified list a, and so on until a is empty.
我不知道标准库中的这种算法,但是一个简单的实现可以是:
I'am not aware of such an algorithm in the Standard Library, but a simple implementation could be:
#include <random>
#include <algorithm>
#include <iterator>
template <class D, class W, class URBG>
void weighted_shuffle
( D first, D last
, W first_weight, W last_weight
, URBG&& g )
{
while (first != last and first_weight != last_weight)
{
std::discrete_distribution dd(first_weight, last_weight);
auto i = dd(g);
if ( i )
{
std::iter_swap(first, std::next(first, i));
std::iter_swap(first_weight, std::next(first_weight, i));
}
++first;
++first_weight;
}
}
实时示例此处.
这篇关于C ++.加权std :: shuffle的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!