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

Question

我有 p 个项目(假设 p=5，items={0,1,2,3,4})。我需要能够以随机顺序迭代它们，但不重复它们(除非所有都被访问过)，同时在迭代之间只保持尽可能小的种子状元数据。否则生成器是无状态的。它将像这样使用:
初始化(在这个例子中元数据很长，但它可以是任何“小”的东西):

long metadata = randomLong()

用法:

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

如果它工作正常，它应该不断返回类似 3, 1, 0, 4, 2, 3, 1, 0, 4, 2, 3 ...
那可能吗？
我知道我可以轻松地预先生成序列，然后元数据将包含整个序列和索引，但这对我来说是不可行的，因为序列将有数千个项目并且元数据必须很小。
我还找到了 this ，这类似于我想要实现的目标，但对我来说要么太简短，要么太数学化。
补充:我知道一个事实，对于 p=1000，有 1000!排序序列的方法，这绝对不适合 long，但是“具有比 long 大的元数据”和“生成器可能无法生成某些序列”对我来说都可以。

Answer 1

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

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++]; 
}