在随机顺序迭代数组

Question

给定一个序列由N个元素组成（例如std :: vector或T *），有没有一种有效的方法以随机顺序迭代其元素，每个元素仅访问一次。解决方案必须避免创建带有洗牌索引的额外数组。

编辑：

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

- Oleg Shirokikh

---

这是否意味着您根本不能有额外的空间，还是只是不能使用预生成的排列？ - Leeor

使用std::shuffle函数进行洗牌，然后从开头到结尾进行迭代。 - Praetorian

Leeor，我在尝试找到一种方法，如何无需使用额外的内存来随机迭代元素，并仍然能够跟踪原始索引 - Oleg Shirokikh

@user2028058：如果我创建一个额外的 bool 标志数组，标记我已经迭代过的元素。严格来说，它不是一个“带有洗牌索引”的数组。但它仍然是一个额外的数组。这样做可以吗？ - AnT stands with Russia

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

- Benjamin Lindley

---

Q是否保证会恰好遍历A的所有元素一次？ - Oleg Shirokikh

@user2028058：是的，它会。 - Benjamin Lindley

我仍在努力弄清楚这是为什么和如何工作的。我不太擅长数学。谢谢！ - WoLfulus

如何避免线性访问？例如：使用一个包含10个元素的数组，当P = 839时，Q将以线性方式从9下降到0。是什么导致了这种情况的发生？ - WoLfulus

@WoLfulus: 是的，它会这样做。每次它都会以相同的增量移动。你只是碰巧选择了一个质数，让该增量为-1。就像我说的那样，它并不特别随机，但通过选择一个质数，你至少可以保证它将穿过所有数字。 - Benjamin Lindley

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;

- CS Pei

---

谢谢，约翰。抱歉，我忘了提到我需要知道当前正在处理的元素的原始索引。谢谢！ - Oleg Shirokikh

创建一个索引向量来代表你的数据，然后对其进行洗牌，接着遍历洗牌后的索引并获取相应的数据元素。 - beldaz

@beldaz：这肯定可以解决问题，但问题是是否有可能避免额外的内存使用（用于索引）。谢谢。 - Oleg Shirokikh

如果你想要一个非确定性（随机）的顺序，你至少需要跟踪你之前访问过的元素，所以我怀疑无法避免一些内存使用。这是纯理论还是你可以放松这些限制？ - beldaz

@beldaz：这是完全实用的 - 在这种情况下，我不关心随机生成器的“纯度”。但我认为你是对的，也许这是不可能的... - Oleg Shirokikh

@user2028058：最好的方法是使用确定性准随机过程。在这种情况下，我认为Benjamin的答案是正确的。https://dev59.com/0HfZa4cB1Zd3GeqPPDop#18994414 - beldaz

Answer 3

嗯，我并不完全清楚制作额外数组的限制。但基本上，我们会随机生成一个索引，然后重复这个过程，如果我们遇到了已经命中的索引，则重新生成。这并不一定是高效的。但是，我敢打赌，界限肯定在O(n^2)和O(n!)之间（可能是O(n^n)）。通过一些工作，我们可以整理出来，并使得界限几乎总是落在n^2上。

- Dylan Lawrence

---

非常低效 :) 但还是谢谢！ - Oleg Shirokikh