我有一个不寻常的问题，以前可能会或可能不会被问过（虽然我什么也没找到，但是我可能只是在寻找错误的流行词）。
我的任务非常简单：给定自然数的“列表”，直到N [0，1，2，… N-1]我都希望重新排列此序列。例如，当我输入数字4时，一个可能的结果将是[3，0，1，2]。随机性应该由某种种子确定（但是，对于大多数公共语言的PRNG，这是标准的）。
天真的方法是只实例化一个大小为N的数组，用数字填充它并使用任何改组算法。
但是，问题在于，这种方法的内存复杂度是O（n），在我的特殊情况下这是很难处理的。我的想法是，编写一个生成器，以迭代方式提供结果列表中的数字。
更准确地说，我需要一些“算法”以迭代方式提供数字。更准确地说，概念类如下所示：
class Generator { // some state int nextNumber(...) { // some magic } }
并迭代调用nextNumber方法可提供序列号（即[0，1，… N-1]的任何排列。当然，此生成器实例的状态应比O（n）具有更好的内存复杂性再一次（我一无所获）。
有什么需要做的算法吗？
您正在寻找的是函数形式的伪随机置换，例如 f ，它以伪随机双射方式将1到N的数字映射到1到N的数字。然后，要生成伪随机排列中的 第n个 数字，只需返回 f（n）
这本质上是与 加密 相同的问题。带密钥的分组密码是伪随机双射函数。如果以某种顺序一次将所有可能的纯文本块送入，它将以不同的伪随机顺序一次一次返回所有可能的密文块。
因此，要解决像您这样的问题，您实际上要做的是创建一个密码，该密码适用于从1到N的数字，而不是256位块或其他任何数字。您可以使用密码学中的工具来执行此操作。
例如，您可以使用Feistel结构（https://en.wikipedia.org/wiki/Feistel_cipher）构造置换函数，如下所示：
由于此函数由多个步骤组成，每个步骤将以双射方式将0到N-1的数字映射到0到N-1的数字，因此整个函数也将具有此属性。如果您输入0到N-1之间的数字，则会以伪随机顺序将它们取回来。
