建立在不断的空间随机排列1..N的 [英] Create a random permutation of 1..N in constant space

问题描述

我期待枚举随机排列在固定空间的数字1..N的。这意味着，我不能存储所有号码在列表中。其原因是，N可以是非常大，超过可用内存。我还是希望能够走过的数字之一，这样的排列在同一时间，来访的每个数字只出现一次。

I am looking to enumerate a random permutation of the numbers 1..N in fixed space. This means that I cannot store all numbers in a list. The reason for that is that N can be very large, more than available memory. I still want to be able to walk through such a permutation of numbers one at a time, visiting each number exactly once.

我知道这是可以做到的某些N：通过他们的整个状态空间随机许多随机数发生器循环，而是完全。与32位国字号良好的随机数生成器会发出数字0的排列。（2 ^ 32）-1。每个数字一次。

I know this can be done for certain N: Many random number generators cycle through their whole state space randomly, but entirely. A good random number generator with state size of 32 bit will emit a permutation of the numbers 0..(2^32)-1. Every number exactly once.

欲来挑N至的任意数在所有和不被限制为2，例如功率。是否有一个算法呢？

I want to get to pick N to be any number at all and not be constrained to powers of 2 for example. Is there an algorithm for this?

推荐答案

最简单的方法可能是只创建一个全范围的PRNG为更大范围的比你所关心的，当它产生比你想有一个数较大，只是把它扔掉，并得到下一个。

The easiest way is probably to just create a full-range PRNG for a larger range than you care about, and when it generates a number larger than you want, just throw it away and get the next one.

另一种可能性是pretty的许多相同的变化是使用线性反馈移位寄存器（LFSR）生成的数字摆在首位。这有几个好处：首先，一个LFSR可能比大多数的PRNG快一点。第二，它是（我相信）容易一点的工程师产生接近你想要的范围内号码的线性反馈移位寄存器，并且仍然是通过数字肯定它的周期在其（伪）随机顺序范围内，没有任何重复。

Another possibility that's pretty much a variation of the same would be to use a linear feedback shift register (LFSR) to generate the numbers in the first place. This has a couple of advantages: first of all, an LFSR is probably a bit faster than most PRNGs. Second, it is (I believe) a bit easier to engineer an LFSR that produces numbers close to the range you want, and still be sure it cycles through the numbers in its range in (pseudo)random order, without any repetitions.

如果没有在细节上花了大量的时间，后面的LFSR算算已经研究很彻底。生产一种在其范围贯穿所有的号码不重复只需要选择一组抽头相对应的不可约多项式的。如果你不想来搜索自己，这是pretty的容易找到已知的对表，几乎任何合理的大小（例如，做一个快速浏览一下，维基百科的文章列出他们规模达19位）。

Without spending a lot of time on the details, the math behind LFSRs has been studied quite thoroughly. Producing one that runs through all the numbers in its range without repetition simply requires choosing a set of "taps" that correspond to an irreducible polynomial. If you don't want to search for that yourself, it's pretty easy to find tables of known ones for almost any reasonable size (e.g., doing a quick look, the wikipedia article lists them for size up to 19 bits).

如果没记错，有可能过位大小中的至少一个不可约多项式。这相当于一个事实，即在最坏的情况下，你可以创建一个生成器，它具有两倍所需的范围内，所以平均你把自己的（大致）可以生成所有其他号码。由于速度的线性反馈移位寄存器，我猜你能做到这一点，仍然保持完全可以接受的速度。

If memory serves, there's at least one irreducible polynomial of ever possible bit size. That translates to the fact that in the worst case you can create a generator that has roughly twice the range you need, so on average you're throwing away (roughly) every other number you generate. Given the speed an LFSR, I'd guess you can do that and still maintain quite acceptable speed.

这篇关于建立在不断的空间随机排列1..N的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！