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

Question

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

我

考虑过洗牌函数，但它只是我关心的索引;数组中的值是任意的，但它们对应的索引很重要。我有一个 1 的矩阵，我需要随机选择一个索引并将该 1 转换为 0。但是我不想执行此计算超过必要的次数（与矩阵中的元素数量完全相同）。

Answer 1

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

1. 生成第二个数组，大小也为 N 。
2. 使用 Fisher-Yates-Knuth 洗牌对第二个数组进行洗牌。
3. 按照第二个数组指定的顺序利用第一个数组的元素。

Fisher-Yates-Knuth shuffle 可以按如下方式实现：

//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));

Answer 2

因此，您需要创建一个值列表，然后将它们洗牌。

虽然有一个随机播放功能，但算法很简单。从索引 0 开始，用 0 到 N-1 范围内的随机值交换，然后转到索引 1 并使用 1 到 N-1 范围内的随机值交换，依此类推，不要交换 0 到 N-1，因为这不提供真正的随机排列。