c++ - 以随机顺序遍历数组

Question

给定一系列N元素（比如std::vectoror T*），是否有任何有效的方法可以以随机顺序迭代其元素，只访问每个元素一次。解决方案必须避免创建带有混洗索引的额外数组。

编辑：

我们还需要能够跟踪原始索引

Answer 1

不是特别随机，但鉴于您的限制，您几乎没有选择。

A is the array
S is the size of the array
Generate a random prime number (P), such that P > S
Q = P % S
for i = 1 to S
    process A[Q]
    Q = (Q + P) % S

Answer 2

使用std::random_shuffle，因此您的代码将如下所示：

std::random_shuffle ( myvector.begin(), myvector.end() );  // in place no extra array
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
   std::cout << ' ' << *it;

Answer 3

好吧，我对制作额外数组的限制并不完全清楚。但本质上，我们随机生成一个索引，然后重复，如果我们命中了我们已经命中的索引，则重新生成。它不一定有效。但是，我冒险猜测这个界限肯定在 O(n^2) 和 O(n!) 之间（可能是 (O(n^n))）。通过一些工作，我们可以清理它并得到几乎总是落在 n^2 上。