15,936,169 members
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
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

## Solution 1

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.

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

v3
Sandeep Mewara 19-May-11 3:09am
OP accepts it or not... here is my 5! :)
Dalek Dave 19-May-11 3:45am
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)

Top Experts
Last 24hrsThis month
 Pete O'Hanlon 40 OriginalGriff 40 Richard Deeming 20 CHill60 10
 OriginalGriff 680 Pete O'Hanlon 570 Richard Deeming 475 merano99 215 Dave Kreskowiak 170

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