Click here to Skip to main content
15,936,169 members
Please Sign up or sign in to vote.
3.00/5 (1 vote)
See more:
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?
Posted
Comments
Sergey Alexandrovich Kryukov 18-May-11 19:55pm    
Of course there is a way. Isn't a nice simple exercise for you? Try is and ask a question if you face a problem.
--SA

1 solution

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]
 
Share this answer
 
v3
Comments
Sandeep Mewara 19-May-11 3:09am    
OP accepts it or not... here is my 5! :)
Dalek Dave 19-May-11 3:45am    
Good Answer.
Peter_in_2780 19-May-11 4:04am    
You'd like this Excel variant of the dumb one. Col A: 1, 2, 3 ... N Col B: =rand(), cloned N times.
Sort on col B, then delete col B. I use it to randomise a list of topics that are all to be covered, but not in a predictable order (ie different from last semester).
Member 1415146 20-May-11 18:52pm    
Thanks. I figured I needed to make my own PRNG, but wasn't really sure how to do that with varying N. Realistically N will be two numbers multiplied together, each number being either between 1 and 10, a multiple of 2 between 10 and 20, or a multiple of 5 between 10 and 50. Hence it seems a=421, c=11 works for all possible cases. What I'd really like to have though is to repeat this and get a different sequence multiple times...
Peter_in_2780 20-May-11 18:59pm    
Different parameters => different sequences. If you want to do it the hard way, calculate a and c each time on the fly. However, your largest possible N appears to be 2500, so I'd recommend the dumb way, remembering to seed your "real" PRNG with, say, time() so you get different sequences.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900