如何从 C 容器中获取随机元素？

Question

从 STL 范围中获取 [pseudo-]random 元素的好方法是什么？

我能想到的最好的办法是做 std::random_shuffle(c.begin(), c.end()) 然后从 c.begin() 中取出我的随机元素。

但是，我可能想要来自 const 容器的随机元素，或者我可能不想要完全洗牌的成本。

有没有更好的办法？

原文由 paperjam 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

C++17 std::sample

这是一种无需重复即可获得多个随机元素的便捷方法。

主文件

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>

int main() {
    const std::vector<int> in{1, 2, 3, 5, 7};
    std::vector<int> out;
    size_t nelems = 3;
    std::sample(
        in.begin(),
        in.end(),
        std::back_inserter(out),
        nelems,
        std::mt19937{std::random_device{}()}
    );
    for (auto i : out)
        std::cout << i << std::endl;
}

编译并运行：

 g++-7 -o main -std=c++17 -Wall -Wextra -pedantic main.cpp
./main

输出：从 1, 2, 3, 5, 7 中选取 3 个随机数，不重复。

For efficiency, only O(n) is guaranteed since ForwardIterator is the used API, but I think stdlib implementations will specialize to O(1) where possible (eg vector ）。

在 GCC 7.2、Ubuntu 17.10 中测试。 如何在 16.04 中获得 GCC 7 。

原文由 Ciro Santilli OurBigBook.com 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

我在其他人引用的 Google+ 文章上发布了这个解决方案。在这里发布它，因为它比其他的稍微好一点，因为它通过使用 std::uniform_int_distribution 避免了偏见：

 #include  <random>
#include  <iterator>

template<typename Iter, typename RandomGenerator>
Iter select_randomly(Iter start, Iter end, RandomGenerator& g) {
    std::uniform_int_distribution<> dis(0, std::distance(start, end) - 1);
    std::advance(start, dis(g));
    return start;
}

template<typename Iter>
Iter select_randomly(Iter start, Iter end) {
    static std::random_device rd;
    static std::mt19937 gen(rd());
    return select_randomly(start, end, gen);
}

样品用途是：

 #include <vector>
using namespace std;

vector<int> foo;
/* .... */
int r = *select_randomly(foo.begin(), foo.end());

我最终 按照类似的方法创建了一个具有更好设计的要点。

原文由 Christopher Smith 发布，翻译遵循 CC BY-SA 3.0 许可协议