C++ : Create unique random distributions 1000 times with no repeated numbers in any distribution

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
}

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