像Python中的random.sample一样提高随机采样能力

Question

我正在尝试使用C++来模仿Python。

random.sample(a_set, n_samples)

C++函数的用法类似于

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

在我自己写之前，是否有任何库可用于此？我的电脑上装有boost 1.46。

- Alfred Zhong

---

如果我理解正确的话，您需要一个函数来生成n_samples个唯一的随机数，是吗？ - Kiril Kirov

@KirilKirov 从 “a_set” 的总体中选择“n_samples”个唯一的元素。 - Bakuriu

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) 中随机地复制 n 个元素到区间 [out, out + n) 中。输入区间中的每个元素最多出现一次于输出区间，采样是均匀概率的。

不幸的是，Matt Austern 提出了几种额外的算法（大多来自 SGI 的原始 STL 实现标准库），其中包括 "random_sample" 和 "random_sample_n"。 (摘自 N3925) 但是...

在Sophia-Antipolis会议上，经过WG21的考虑，Austern更新了提案，生成了[N2666]。除了其他改动外，他撤回了采样算法，因为“LWG担心它们可能不被足够理解以进行标准化...可能适合为TR2提出这些算法”。随后，LWG以10-1、2个弃权的支持率达成了坚定的共识，支持将这些算法列入未来的技术报告（现称为技术规范）。random_sample_n算法的一个版本已经进入库基础组件TS，称为std::experimental::sample，提案的最新版本N3925在2014年02月被采用，但仍未成为标准（可能在C++17中）。

除了蓄水池抽样算法外，你还可以查看 Donald Knuth 在《计算机程序设计艺术》第二卷第3.4.2节中阐述的众所周知的“S算法”（“选择抽样技术”）。

- manlio

Answer 2

您想要解决的问题被称为蓄水池抽样。我尝试搜索“蓄水池抽样c++实现”，但是通过结果的粗略浏览并没有找到实际的库。该算法非常简单，学习和自己编写也很有趣，因此我建议您这样做。

- dshin