c++ - 如何使用 Mersenne Twister 生成两个数字之间的所有值恰好一次

Question

我想使用 mt19937 遍历一个数组并从中获取每个值一次，但顺序是随机的。本质上，有没有一种方法可以使用 mt19937 仅生成一次特定范围内的所有数字(不只是忽略重复项，而是确保它不会完全产生重复项(为了提高效率))？

我考虑过随机播放功能，但它只是我关心的索引；数组中的值是任意的，但它们对应的索引很重要。我有一个 1 的矩阵，我需要随机选择一个索引并将该 1 变为 0。但我不想执行此计算超过必要的次数(与矩阵中的元素一样多)。

Answer 1

假设您的数组大小为 N，并且您不想重新排列它:

1. 生成第二个数组，大小也是 N。
2. 使用 Fisher-Yates-Knuth shuffle 打乱第二个数组.
3. 按照第二个数组指定的顺序使用第一个数组的元素。

Fisher-Yates-Knuth 洗牌可以按如下方式实现:

//To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
  j ← random integer such that i ≤ j < n
  swap a[i] and a[j]

你也可以使用 std::shuffle :

std::shuffle(a.begin(), a.end(), std::default_random_engine(seed));