伪随机序列长度N [英] Pseudorandom sequence length N

问题描述

有没有一种方法可以生成长度为N的整数的伪随机序列，其中该序列中包含从0到N-1的所有整数. N是一个任意且可变的数字吗?

解决方案

简短答案:是.

真正的哑巴方式(但如果N小则可能很好):
创建一个由整数0 .. N-1
组成的数组 随机播放(随机交换两个*项目)
缺点-O(N)的空间和时间要求.
* 使用您已有的任何PRNG，将其截断或缩放为N

更聪明的方式:
快速构建全周期伪随机发生器
为简单起见，请选择混合的全等PRNG X n + 1 =(a * X n + c)mod N
现在，您的任务是选择a，c和X 0 ，它们都在0..N-1
范围内 整个时期的要求是:
c是N的素数-如果c是素数，那很容易
(a-1)可被N的所有素数整除 (a-1)是4的倍数，如果N是4的倍数(即上面的行以4为质数！)

解决这些问题需要一些数字运算，但还算不错.
生成的PRNG的统计质量可能不太好，但是如果您真正需要的只是0..N-1的随机变化，则可能无关紧要.

如果您需要更多的数学背景，请在线性同余生成器"上查找维基百科以及从那里链接的其他页面.

干杯，
彼得
如果这回答了您的问题，请接受.还是投票吧.

愚蠢的我-忘记了公式中的()modN. [/edit]

Is there a way of generating a pseudorandom sequence of integers length N, where all integers from 0 to N-1 are included within the sequence. N to be an arbitrary and variable number?

解决方案

Short answer: yes.

Real dumb way (but can be good if N is small):
Create an array of the integers 0 .. N-1
Shuffle it (swap two random* items some large number of times)
Downside - O(N) space and time requirements.
* using whatever PRNG you already have, truncated or scaled to N

Smarter way:
Construct a full-period pseudorandom generator on the fly
For simplicity, choose a mixed congruential PRNG Xn+1 = (a * Xn + c) mod N
Your task is now to select a, c and X0, all in the range 0..N-1
The requirements for full period are:
c is relatively prime to N - if c is prime, that''s easy
(a-1) is divisible by all prime factors of N
(a-1) is a multiple of 4 if N is a multiple of 4 (i.e. consider 4 a prime for the line above!)

It''s a bit of number-crunching to work these out, but not too bad.
The statistical quality of the resulting PRNG is not likely to be very good, but that probably won''t matter if what you really need is just a shuffle of 0..N-1.

Look up wikipedia on ''linear congruential generator'' and other pages linked from there if you want more math background.

Cheers,
Peter
If this answers your question, accept it. Vote anyway.

[edit] Silly me - forgot the ( ) mod N in the formula. [/edit]

这篇关于伪随机序列长度N的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！