是否可以以随机顺序迭代数组？

Question

所以，假设我有一个数组：

int arr[5];

是否可以按随机顺序迭代数组，而不是从 0 到 4 迭代数组，并且迭代器不会两次遍历同一位置？

Answer 1

以下所有内容都假设您想在 O(1) 空间中实现迭代 - 不使用例如索引的辅助数组，您可以对其进行洗牌。如果你能负担得起 O(n) 空间，解决方案相对简单，所以我假设你只能负担 O(1) 空间。

要以随机方式迭代数组，您可以创建一个随机数生成器，并将其输出用作数组的索引。您不能以这种方式使用标准 RNG，因为它们可能会过快地输出相同的索引两次。然而，RNG 的理论相当广泛，并且至少有两种类型的 RNG 其周期有保证。

• 线性反馈移位寄存器
• Lehmer 随机数生成器

使用这些理论思想：

1. 选择一个数字 N ≥ n（其中 n 是数组的大小），但不要比 n 大很多，这样就可以构造一个周期为 N 的 RNG
2. 调用 RNG N 次，因此它会生成从 0 到 N-1 的数字排列
3. 对于每个数字，如果它小于数组的大小，则输出具有该索引的数组元素

制作给定周期的 RNG 的技术可能太烦人，无法在代码中实现。因此，如果您事先知道数组的大小，则可以选择 N = n，并手动创建 RNG（第一步因式分解 n 或 n+1）。如果您不知道数组的大小，请选择一些易于使用的数字作为 N，例如一些合适的 2 的幂。

Answer 2

正如评论中提到的，有多种方法可以做到这一点。最明显的方法是仅

shuffle

范围，然后迭代它：

std::shuffle(arr, arr + 5);

for (int a : arr) 
  // a is a new random element from arr in each iteration

这当然会修改范围，这可能不是你想要的。

---

对于不修改范围的选项：您可以生成一系列索引，打乱这些索引并使用这些索引来索引该范围：

int ind[5];
std::iota(ind, ind + 5, 0);
std::shuffle(ind, ind + 5);

for (int i : ind)
  // arr[i] is a new random element from arr in each iteration

---

您还可以实现一个自定义迭代器，以随机顺序迭代某个范围而不重复，尽管这对于您想要实现的功能来说可能有点过头了。尝试一下、了解其工作原理仍然是一件好事。