c++ - 使用 128 位种子的伪随机排列

Question

我正在寻找一些函数，这些函数可以通过使用 128 位 key 作为种子来高效地置换 vector 的索引。优化对我来说至关重要，因为我多次执行相同的操作。

谁能推荐一个 C/C++ 开源库，其中可以使用 128 位播种并且它支持 permute(seed, range(min,max),sample_size) 之类的函数？

例如；如果 permute(1, [0,10], 10) 函数给出的结果为:3 6 7 2 4 9 8 1 0 5，然后 permute(1, [0,10], 5) 应该给出 3 6 7 2 4。

min、max 和 sample_size 参数是动态变量。它在每次迭代时都会发生变化。

Answer 1

您可以使用 Fisher–Yates_shuffle :

// Fisher–Yates_shuffle
std::vector<int>
FisherYatesShuffle(std::size_t size, std::size_t max_size, std::mt19937& gen)
{
    assert(size < max_size);
    std::vector<int> res(size);

    for (std::size_t i = 0; i != max_size; ++i) {
        std::uniform_int_distribution<> dis(0, i);
        std::size_t j = dis(gen);
        if (j < res.size()) {
            if (i < res.size()) {
                res[i] = res[j];
            }
            res[j] = i;
        }
    }
    return res;
}

Live example