迭代器产生唯一的随机顺序？

Iterator to produce unique random order?

问题陈述如下，我们有大量的项目是通过迭代器模式（动态构造或获取）遍历请求的项目。

由于项目数量较多，无法保存在内存中（以列表为例）

What is a procedure for the iterator to follow in order to produce a random order of the items each time the iterator is called. A unique random order means that eventually all items are traversed only once but returned in a random order.

如果物品数量比较少，可以按如下方式解决：

  1. 将项目存储在内存（或辅助内存）中的列表中
  2. Shuffle 列表
  3. 遍历打乱后的列表。

对于这个问题，可以假设迭代器可以索引项目（或 rank/unrank 它们）。因此迭代器可以为项目范围内的所有索引 i 获取第 i 个项目。

注意随机顺序应该均匀分布在所有项目排序的集合中，或者换句话说是无偏的。这个条件遗漏了在逐块方案中随机化项目列表的解决方案（例如为了在内存中有一些项目并只随机化它们，然后是下一个项目块等等）

加密是可逆的，因此加密是从集合到自身的一对一映射。

选择一个块大小足以覆盖您拥有的项目数量的块密码。

加密数字 0、1、2、3、4，...这将为您提供一个不重复的有序数字列表，最大为 2^（块大小）。

如果加密数字太大，请忽略。如果加密数字在您的项目列表的大小之内，则选择该项目。对您需要的任何物品重复上述步骤。

具有可变块大小的密码（如 Hasty Pudding 密码）将减少未命中的次数。

我会提供解决这个问题的方案如下：

重点是对（后继）索引进行编码以生成随机顺序。

因为（可逆）加密就是这样一种方案。

让我们看看这些方案的大致轮廓：

假设迭代器使用后继函数来获取下一个index/item。对于通常的情况，后继函数将是：

def succ(index):
   return index+1

这 return 是下一个索引。如果将其视为二进制操作，index+1 代码会从当前索引模式中创建一个新的索引模式（因为缺少更好的词）。

大概可以概括这种模式（在二元运算中，即 logN）以创建一个后继函数，该函数 return 是下一个索引，但以随机或随机的唯一顺序遍历。

例如加密例程可以看作是这样一种方案。

一个更简单的方案是使用模块化算法，类似于伪随机数生成器，具有合适的参数，即：

def succ_rand_modulo(index):
   return (seed*index+step) mod numItems

适合选择seed和step（例如relatively prime并且足够大）数字，以便产生具有统一 属性 的随机排序（即 无偏 ）

上面的线性映射可能不会产生所有的顺序，可以假设多项式映射有更多的自由参数来调整，可以产生所有的permutations/orderings（见：Permutation Polynomials (over finite fields)）

实际上，所有这些方法都是对索引进行重新编码的方法（即加密、模运算、伪随机生成、二进制操作等）。

我要说的是，最有效的方法是（多项式）模型（即伪随机数生成），前提是参数是适当地选择以产生A uniform/unbiased所有随机排序的分布（见上文）。

更新：

另一种只需要将 numItems 位存储在内存中（但需要更多时间）的方法是 基于拒绝的 方法。可以随机生成或获取一个 index/item 并将位向量上的关联位设置为 1（获取项目），然后生成另一个随机索引，如果设置了关联位（索引已被使用）拒绝它并重新-产生另一个随机索引等等。平均而言，这将有 O(numItems) 的 运行 时间，但最坏的情况可能会很长。

更新 2：

另一个有前途的方法，在各种情况下也是最优的，是 method by I. STOJMENOVIC 到 rank/unrank 组合旋转对象均匀有效地计算大整数。

该方法适用于这种情况，随机排序只是所有排序之间的排列。因此，要生成任何随机排序，需要尝试生成 N! 项的随机排列。能够均匀地（即无偏见地）生成随机排列并且不处理大整数是一个加号。 STOJMENOVIC 的方法，只使用 [0,1] 中的一个随机数，并将其作为生成特定排列的概率。为了在这种情况下调整方法，我们将代码更改为 return 一次排列的一个元素（保持生成器在任何给定时间的某种状态）仅使用单个随机数的初始种子在 [0,1].

Lecture notes on Lexicographic generation (touching upon random generation as well).

关于相同问题/类似方法的参考资料：

基于唯一随机数生成的方案

  1. How to Generate a Sequence of Unique Random Integers
  2. List of random number generators (wikipedia)
  3. GNU, Random number generator algorithms
  4. Generating combinatorial objects without computing large integers

Cryptography/Cipher 基于方案

  1. Hasty-Pudding cipher
  2. Block cipher

基于编码的方案/数论方案

  1. Coding theory
  2. Linear Code
  3. Permutation Polynomials (over finite fields)