用于迭代随机非重复序列的生成器

Question

我有 p 个项目（假设 p=5，项目={0,1,2,3,4}）。我需要能够以随机顺序迭代它们，但不重复它们（除非所有都被访问过），同时在迭代之间只保留尽可能小的类似种子的元数据。生成器在其他方面是无状态的。它会像这样使用：

初始化（本例中的元数据很长，但它可以是任何“小”的东西）：

long metadata = randomLong()

用法：

(metadata, result) = generator.generate(metadata)
return(result)

如果它正常工作，它应该连续 return 类似 3, 1, 0, 4, 2, 3, 1, 0, 4, 2, 3...

这可能吗？

我知道我可以很容易地预先生成序列，然后元数据将包含整个序列和一个索引，但这对我来说不可行，因为序列将包含数千个项目并且元数据必须很小。

我还发现了 this，它与我想要实现的目标相似，但对我来说要么太简短要么太数学化。

补充：我知道一个事实，对于p=1000，有1000！排序序列的方式，这绝对不适合长，但是“元数据大于长”和“生成器可能无法生成一些序列”对我来说都可以。

Answer 1

作为基础，我会使用 Fisher-Yates algorithm。它能够构建 O(n) 中给定有序元素列表的随机排列。然后诀窍可能是构造一个迭代器，该迭代器对内部元素列表进行洗牌并对其进行迭代，当此 internal 迭代结束时，再次洗牌并迭代结果...

类似于：

function next() -> element {
  internal data:
    i an integer;
    d an array of elements;

  code:
    if i equals to d.length { shuffle(d); i <-- 0; }
    return d[i++]; 
}

用于迭代随机非重复序列的生成器

Generator for iterating over a random non-repeated sequence

random

algorithm

sequence