迭代生成自然数的排列

您正在寻找的是函数形式的伪随机置换，例如 f ，它以伪随机双射方式将1到N的数字映射到1到N的数字。然后，要生成伪随机排列中的 第n个
数字，只需返回 f（n）

这本质上是与 加密
相同的问题。带密钥的分组密码是伪随机双射函数。如果以某种顺序一次将所有可能的纯文本块送入，它将以不同的伪随机顺序一次一次返回所有可能的密文块。

因此，要解决像您这样的问题，您实际上要做的是创建一个密码，该密码适用于从1到N的数字，而不是256位块或其他任何数字。您可以使用密码学中的工具来执行此 *** 作。

例如，您可以使用Feistel结构（https://en.wikipedia.org/wiki/Feistel_cipher）构造置换函数，如下所示：

1. 令W为floor（sqrt（N）），令函数输入为x
2. 如果x <W ^ 2，则将x分为2个字段，从0到W-1：h = floor（x / W）和l = x％W。哈希h以产生从0到W-1的值，并设置l =（l + hash）％W。然后交换字段-让x = l * W + h
3. x =（x +（NW ^ 2））％N
4. 重复步骤（2）和（3）几次。您做得越多，结果看起来就越随机。步骤（3）确保在许多回合中x <W ^ 2为真。

由于此函数由多个步骤组成，每个步骤将以双射方式将0到N-1的数字映射到0到N-1的数字，因此整个函数也将具有此属性。如果您输入0到N-1之间的数字，则会以伪随机顺序将它们取回来。