以随机顺序迭代数组

Question

给定一系列N元素(比如std::vector或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;