C++：创建独特的随机分布 1000 次，任何分布中都没有重复的数字

Question

问题：

我的数字范围是 1 到 20,000。我想对范围内 8 个不同数字的均匀分布进行 1000 次采样。每个分布不应有重复的数字。此外，1000 个分布中的每个分布都必须是唯一的（在对所有获得的分布进行字母顺序排序后，从技术上讲，没有两个分布应该具有相同的数字序列）。

我做了什么：

我遇到了std::uniform_int_distribution<int>C++ 11 标准。因此尝试以下代码来测试其在不同范围内的唯一性。

#include <iostream>
#include <random>

int main(int, char*[]) {
    const int range_from  = 0;
    const int range_to    = 20000;
    std::random_device                  rand_dev;
    std::mt19937                        generator(rand_dev());
    std::uniform_int_distribution<int>  distr(range_from, range_to);

    for(int i = 0; i < 1000; ++i){ //Iteration for maximum distributions

        for (int j = 0; j < 8; ++j) //Iteration for random distribution generation
            std::cout << distr(generator) << '\n';
    }
}

不同尝试获得的输出

Attempt 1:      Attempt 2:

16102           6656
540             10316
8718            12251
18059           1254
10976           3982
18391           12857
14748           9253
12137           3335

一些事实：

根据两次尝试，输出看起来是唯一的。我还意识到，可以有 20,000C8 = 20,000!/(8!x19,992!) 这样可能的分布，这些分布可以是唯一的（每个分布中没有相同的数字，并且当我们进行字母排序时没有重复的分布）。

我的问题：

这段代码真的能以当前的形式实现我想要做的事情吗？或者我应该做一些昂贵的验证过程，例如对每个发行版进行字母顺序排序，并将它们中的每一个记录在一个中，std::vector并检查发行版是否已经存在？

后一个过程非常昂贵并且需要大量的计算时间。您会建议任何替代/更好的方法吗？

Answer 1

如果您希望这 1000 组 8 个随机数是唯一的，那么您可以生成所需的所有值，将它们随机化，然后将随机集中的前 8000 个值作为您的 1000 组 8 个随机数。

int main()
{
    const int range_from  = 0;
    const int range_to    = 20000;
    std::vector<int> values(range_to - range_from);

    std::generate(values.begin(), values.end(), [value = range_from]() mutable { return value++; });  
    // values now has 0 to 20000                                                                                            
    std::shuffle(values.begin(), values.end(), std::mt19937{std::random_device{}()});
    // now it is a random order

    values.resize(8000);
    // now we have the 8000 random numbers in the range 0 to 20000
}

在这种情况下，这并不算太浪费，但如果您的范围足够大并且您想要的组数足够小，您可能需要选择不同的解决方案。否则你会浪费很多空间。