给定一个序列由N个元素组成(例如std :: vector或T *),有没有一种有效的方法以随机顺序迭代其元素,每个元素仅访问一次。解决方案必须避免创建带有洗牌索引的额外数组。
编辑:
我们还需要能够跟踪原始索引。
编辑:
我们还需要能够跟踪原始索引。
虽然不是特别随机,但考虑到你的限制,可选项并不多。
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
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;
嗯,我并不完全清楚制作额外数组的限制。但基本上,我们会随机生成一个索引,然后重复这个过程,如果我们遇到了已经命中的索引,则重新生成。这并不一定是高效的。但是,我敢打赌,界限肯定在O(n^2)和O(n!)之间(可能是O(n^n))。通过一些工作,我们可以整理出来,并使得界限几乎总是落在n^2上。
std::shuffle
函数进行洗牌,然后从开头到结尾进行迭代。 - Praetorianbool
标志数组,标记我已经迭代过的元素。严格来说,它不是一个“带有洗牌索引”的数组。但它仍然是一个额外的数组。这样做可以吗? - AnT stands with Russia