迭代生成自然数的排列 [英] Iteratively generating a permutation of natural numbers
问题描述
我有一个不寻常的问题，这个问题以前可能没有问过(虽然我什么也没找到，但是我可能只是在寻找错误的流行词).
I have a somewhat unusual question, that may or may not have been asked before (I did not find anything though, however I might just have looked for the wrong buzzwords).
我的任务非常简单:给定自然数的列表"，直到N [0，1，2，... N-1]，我想重新排列此序列.例如.当我输入数字4时，一个可能的结果将是[3，0，1，2].随机性应该由某种种子确定(但这是大多数PRNG用通用语言编写的标准).
My task is pretty simple: Given the "list" of natural numbers up to an N [0, 1, 2, ... N - 1] I want to shuffle this sequence. E.g. when I input the number 4, one possible result would be [3, 0, 1, 2]. The randomness should be determinable by some seed (which however is standard to most PRNGs in common languages).
天真的方法是只实例化一个大小为N的数组，用数字填充并使用任何改组算法.
The naive approach would be to just instantiate an array of size N, fill it with the numbers and use any shuffling algorithm.
但是，问题是这种方法的内存复杂度是O(n)，在我的特殊情况下这是很难处理的.我的想法是，编写一个生成器，以迭代方式提供结果列表中的数字.
The problem however is, that the memory complexity of this approach is O(n), which in my special case is not tractable. My idea is, to write a generator that iteratively provides the numbers in the resulting list.
更准确地说，我需要一些算法"以迭代方式提供数字.更准确地说，概念类将如下所示:
To be more precise I want some "algorithm" that provides the numbers in an iterative fashion. To be more precise, a conceptual class would look like this:
class Generator {
// some state
int nextNumber(...) {
// some magic
}
}
并迭代调用nextNumber方法提供序列号(即[0，1，... N-1]的任何排列.当然，此生成器实例的状态应比O更好的内存复杂性(n)再说一次(我什么也得不到).
And calling the nextNumber method iteratively provides the numbers of the sequence (i.e. any permutation of [0, 1, ... N - 1]. Of course that state of this generator instance should have a better memory complexity than just O(n) again (I would gain nothing).
有什么需要做的算法吗?
Is there any algorithm to do, what I desire?
推荐答案
您正在寻找的是函数形式的伪随机排列，例如 f ，该函数映射从1开始的数字以伪随机双射的方式从N到N到1到N的数字上.然后，要生成伪随机排列的 n 个数字，只需返回 f(n)
What you are looking for is a pseudo-random permutation in the form of a function, say f, that maps numbers from 1 to N onto numbers from 1 to N in a pseudo-random bijective way. Then, to generate the nth number in a pseudo-random permutation, you just return f(n)
这与加密本质上是相同的问题.带密钥的分组密码是伪随机双射函数.如果您以某种顺序一次将所有可能的纯文本块送入，它将以不同的伪随机顺序一次一次返回所有可能的密文块.
This is essentially the same problem as encryption. A block cipher with a key is a pseudo-random bijective function. If you feed it all possible plaintext blocks exactly once in some order, it will return all possible ciphertext blocks exactly once in a different, pseudo-random order.
因此，要解决像您这样的问题，您实际上要做的是创建一个密码，该密码适用于从1到N的数字，而不是256位块或其他任何数字.您可以使用密码学中的工具来做到这一点.
So to solve a problem like yours, what you essentially do is create a cipher that works on numbers from 1 to N instead of 256-bit blocks or whatever. You can use the tools from cryptography to do this.
例如，您可以使用Feistel结构构造置换函数( https://en.wikipedia. org/wiki/Feistel_cipher )，就像这样:
For example, you can construct your permutation function with a Feistel structure (https://en.wikipedia.org/wiki/Feistel_cipher) like this:
- 让W为floor(sqrt(N))，让该函数的输入为x
- 如果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
- x =(x +(N-W ^ 2))％N
- 重复步骤(2)和(3)几次.您做得越多，结果看起来就越随机.步骤(3)确保x ＜0. W ^ 2在许多回合中都是正确的.
由于此函数由多个步骤组成，每个步骤都将以双射的方式将0到N-1的数字映射到0到N-1的数字，因此整个函数也将具有此属性.如果您输入0到N-1之间的数字，则会以伪随机顺序将它们取回来.
Since this function consists of a number of steps, each of which will map the numbers from 0 to N-1 onto the numbers from 0 to N-1 in a bijective way, the entire function will also have this property. If you feed it the numbers from 0 to N-1, you'll get them back out in a pseudo-random order.
这篇关于迭代生成自然数的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
