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]

15,936,169 members

--SA