从集合中重复伪随机选择的算法，无需频繁重复

Question

我有一个数组（概念上是一个集合，但让我们将其实现为一个数组），例如 [A，B，C，D，E，F]。

我需要一种算法，可以从数组中伪随机地选取一个项目，这样在 x 次迭代内就不会选取任何项目两次。

也就是说，如果该数组的 x 为 3，则可以：F, C, B, D, F, E, A, B,...

这不行：F，C，D，C，...

除了这个限制之外，选择应该尽可能随机。 （例如，简单地打乱数组并在其副本中进行选择是不可接受的。）

理想情况下，无需记录所有先前的选择即可实现此目的。

因此该函数的结构如下：

function pick(options, minspacing, iteration) {...}

（将用JavaScript实现）。

Answer 1

这似乎符合要求：首先，随机选择

x

元素并将它们移动到数组的开头。然后，在每次迭代中

i

：

• 在 [i, N)

   中随机选择一个索引 

  j
• 将

  A[j]

  与

  A[i%x]

交换
• 返回

  A[i%x]

  。直到经过

  x

  更多迭代后，它才会被交换回可选择范围。