尝试每次迭代生成一个独特的随机数序列

Question

正如标题所述,我每次运行这个小程序时都会尝试创建一个独特的随机数序列.

但是,有时我得到的结果如下:

102
201
102

代码

#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

int main() {
        for (int i = 0; i < 3; i++) {
                srand (time(NULL)+i);
                cout << rand() % 3;
                cout << rand() % 3;
                cout << rand() % 3 << '\n' << endl;
        }
}

很明显,srand没有我想要的神奇功能.我希望这有一个合乎逻辑的黑客呢？

编辑1:为了澄清,这只是一个简单的测试程序,用于更大规模的实施.因此,不是rand%3的3次迭代,而是运行1000或更多rand%50.如果我在其操作的某个时刻看到102,我会想要它,以便我再也看不到102.

Answer 1

首先,如果您打算使用srand/ rand,您希望在每次执行程序开始时将其播种一次(并且只播放一次):

int main() {
    srand(time(NULL));
    for (int i = 0; i < 3; i++) {
    cout << rand() % 3;
    cout << rand() % 3;
    cout << rand() % 3 << '\n' << endl;
}

其次,time通常只产生分辨率为1秒的结果,因此即使使用此校正,如果在同一秒内运行程序两次,您可以预期它在两次运行中产生相同的结果.

第三,你真的不想使用srand/ rand反正.随机数生成器<random>通常要好得多(并且可能更重要的是,定义得足够好,它们代表了更为人熟知的数量).

#include <random>
#include <iostream>

int main() { 
    std::mt19937_64 gen { std::random_device()() };
    std::uniform_int_distribution<int> d(0, 2);

    for (int i = 0; i < 3; i++) {
        for (int j=0; j<3; j++)
            std::cout << d(gen);
        std::cout << "\n";
    }
}

然而,根据编辑,这仍然是不够的.你真正想要的是一个没有重复的随机样本.要做到这一点,你需要做的不仅仅是生成数字.随机生成的数字不仅可以重复,而且如果你产生足够数量,它们将不可避免地重复(但重复的可能性变得非常高,即使它还不可避免).

只要您生成的结果数量与可能结果的数量相比较小,您可以非常轻松地将结果存储在生成它们的集合中,并且仅将结果视为实际输出(如果之前不是出现在集合中:

#include <random>
#include <iostream>
#include <set>
#include <iomanip>

int main() {
    std::mt19937_64 gen { std::random_device()() };
    std::uniform_int_distribution<int> d(0, 999);
    std::set<int> results;

    for (int i = 0; i < 50;) {
        int result = d(gen);
        if (results.insert(result).second) {
            std::cout << std::setw(5) << result;
            ++i;
            if (i % 10 == 0)
                std::cout << "\n";
        }
    }
}

如果结果的数量接近可能结果的数量,则这变得非常低效.例如,假设您的生成数字从1到1000(因此可能有1000个结果).考虑如果您决定生成1000个结果(即所有可能的结果)会发生什么.在这种情况下,当你产生最后一个结果时,实际上只剩下一种可能性 - 而不仅仅是产生一种可能性,你会产生一个接一个的随机数,直到你偶然发现剩下的一种可能性.

对于这种情况,有更好的方法来完成这项工作.例如,您可以从容纳所有可能数字的容器开始.要生成输出,请在该容器中生成随机索引.您输出该数字,并从容器中删除该数字,然后重复(但这次,容器是一个较小的容器,因此您将随机索引的范围减少一个).这样,您生成的每个随机数都会产生一个输出.

只需改组一组数字就可以做到这一点.这有两个缺点.首先,你需要正确地改变它们 - 一个Fischer-Yates shuffle很好地工作,但是否则很容易产生偏差.其次,除非你实际上使用数组中的所有(或非常接近全部)数字,否则这是低效的.

对于极端情况,请考虑需要一些(例如10个)64位数字.在此,首先使用2 ⁶⁴ -1的数字填充数组.然后你做2 ⁶⁴ -2交换.所以,你只做了大约2 ^65次操作就产生了10个数字.在这种极端的情况下,问题应该是非常明显的.虽然如果每个产生(比方说)1000个32位数字就不那么明显了,但是你仍然有相同的基本问题,只是程度稍低.因此,虽然这是针对少数特定情况执行操作的有效方式,但其适用性相当狭窄.