Boost随机样本，如python random.sample

Question

我正在尝试使用c++来模仿python

random.sample(a_set, n_samples)

像 这样的c++函数

set<string> sample(set<string> input, int n_samples)

在写我自己的库之前，是否有库这样做?我的电脑上有1.46的boost。

Answer 1

从c++ 17开始有std::sample:

std::sample(input.begin(), input.end(), std::back_inserter(out),
            n_samples, std::mt19937{std::random_device{}()});

原来的答案如下。我把它留在这里供参考。

---

SGI实现的STL具有random_sample和random_sample_n功能:

template <class InputIterator, class RandomAccessIterator>
Random AccessIterator random_sample(InputIterator first, InputIterator last,
                                    RandomAccessIterator ofirst,
                                    RandomAccessIterator olast) 
template <class ForwardIterator, class OutputIterator, class Distance>
OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last,
                               OutputIterator out, Distance n)

random_sample_n随机将范围[first, last)中的元素样本复制到范围[out, out + n)中。输入范围内的每个元素在输出范围内最多出现一次，并且以均匀概率选择样本。

不幸的是

Matt Austern提出了几个额外的算法(主要来自SGI的标准库的原始STL实现)。其中包括random_sample和random_sample_n

<一口>(从N3925)

,

经过WG21在Sophia-Antipolis会议上的考虑，Austern更新了提案，产生了[N2666]。在其他变化中，他撤回了抽样算法，因为"LWG担心他们可能没有很好地理解标准化……在TR2中提出这些算法可能是合适的。LWG随后取得了坚实的成绩支持在未来的技术报告(现在称为技术规范)中包含这些算法的共识(10- 1,2 abs.)。

random_sample_n算法的一个版本已经进入了Library Fundamentals TS，并被称为std::experimental::sample，提案N3925的最新迭代于2014-02年被采用，但仍未成为标准的一部分(可能在c++ 17中)。

除了水库采样算法，您还可以看看Donald Knuth在the Art of Computer Programming - Volume 2 -§3.4.2中阐明的著名的算法S("选择采样技术")。

Answer 2

您要解决的问题称为储层取样。我试着在谷歌上搜索"水库采样c++实现"。谷歌为我自动完成了查询，但粗略地浏览一下结果并没有找到一个真正的图书馆。

这个算法非常简单，学习起来很有趣，自己写也很有趣，所以这就是我推荐的。