c++ - 在 C++11 中绘制 n 个随机值的优雅方法？

Question

对于我的程序，到目前为止，我需要不时在 [0..k[ 中绘制 一个 随机值，并使用 C++11 <random>功能真的很好用。我当前的代码类似于

class Random
{
public:
  Random() : rng( rd() ) { }

  inline int getRandNum( int limit ) { return ( numbers(rng) % limit ); } 

private:
  std::random_device rd;
  std::mt19937 rng;
  std::uniform_int_distribution<int> numbers;
};

现在，我需要在 [0..k[.我在 <random> 中找东西允许，但要么我找不到它，要么这样的东西还不存在。有没有比调用我的 getRandNum 函数并重复直到我得到 n 个不同的值更聪明、更优雅的方法来继续？

编辑:给出一个想法，在我的程序中，k 是几千，n 是几十。

Answer 1

此解决方案不是特定于 C++，但可以用任何语言轻松实现。

您想要的基本上是将数字 0 到 k 打乱并选择前 n 个数字，其中 n <= k。这可以使用水库采样算法来完成。请参阅此维基百科 link对于伪代码。

请注意，可以在不存储所有 k 个数字并将它们洗牌的情况下获得 n 个数字。也就是说，可以只使用 O(n) 空间，其中 n 是您希望获得的随机数的数量，而不是 O(k)。如果我们假设生成随机数需要 O(1) 时间，则该算法的时间复杂度为 O(k)。