如何使用C++的uniform_int_distribution进行无重复抽样

Question

我想在c++的随机库中使用uniform_int_distribution，但是它只能进行有放回的随机抽样，就像下面的示例一样。我该如何进行无放回的抽样？

#include <iostream>
#include <random>

int main()
{
  std::default_random_engine generator;
  std::uniform_int_distribution<int> distribution(1,4);

  for(int i=0; i<4; ++i)
    std::cout << distribution(generator) << std::endl;

  return 0;
}

- ywx

---

你的意思是什么，“with replacement”？ - Petr

Answer 1

自c++17起，现在有一个标准库函数可以完美地实现此操作。请参见https://en.cppreference.com/w/cpp/algorithm/sample

#include <iostream>
#include <random>
#include <string>
#include <iterator>
#include <algorithm>

int main()
{
    std::string in = "abcdefgh", out;
    std::sample(in.begin(), in.end(), std::back_inserter(out),
                5, std::mt19937{std::random_device{}()});
    std::cout << "five random letters out of " << in << " : " << out << '\n';
}

- Philip M

Answer 2

使用 std::shuffle 函数，例如在一个初始化为 {1, 2, 3, 4} 的 std::array<int> 或 std::vector<int> 上。然后按顺序读取容器内容。

这比抽取随机数并仅在其之前未出现过时接受更好的统计特性。

参考： http://en.cppreference.com/w/cpp/algorithm/random_shuffle

- Bathsheba

---

我会使用std::shuffle代替。 - ywx

这是一个很好的观点：在使用C++11时最好使用新函数。 - Bathsheba

你能解释一下“更好的统计性质”是什么意思吗？假设你只需要从一个大向量中进行两次无重复抽取。洗牌算法在向量大小方面具有线性复杂度，而另一种建议（抽取并拒绝已经被抽取的）将是O(1)复杂度。 - Joris Bierkens

@quant_dev 在这个意义上，两种算法的统计特性将是相同的... - Joris Bierkens

Answer 3

如果你想要从区间[low, high)中不重复地随机采样N个整数，可以这样写：

std::vector<int> array(N);   // or reserve space for N elements up front
 
auto gen = std::mt19937{std::random_device{}()};
    
std::ranges::sample(std::views::iota(low, high), 
                    array.begin(),
                    N, 
                    gen);

std::ranges::shuffle(array, gen);  // only if you want the samples in random order 

这里有一个演示。

这类似于Philip M的答案，但是从C++20开始，可以懒惰地生成输入范围。

- cigien