Pseudo random number generator with > 64 bit seed for a 52 card deck shuffle

Question

While writing a card shuffling algorithm I realized that there are 52! ~= 2^225 possible shuffles that can occur. Given this, it seems to me that any shuffling algorithm based on a PRNG with a standard 32 bit or 64 bit seed would only be capable of producing a subset of all possible shuffles. Since my platform only has a 32 bit seeded PRNG (just the POSIX srandom()/random() functions), I was wondering if there is any way to creatively use this to create a shuffling algorithm capable of producing any result. If not, does anyone know of a PRNG algorithm capable of using a seed which is a composite of several 32 bit integers which I could implement myself?

Answer 1

If you want to solve your problem using the current random number generator, you just have to find a way to divide the parameter space of all possible card shuffles into groups.

For example, if you had a random seed that could only be 1 through 4, but a parameter space that had 12 possible permutations, you would solve using two random seeds:

(seed1) defines which parameter group you were in (1-4,5-8, or 9-12)
(seed2) defines which element is your final result

(The parameter set does not have to be an even multiple of the seed size for this to work.)

I used this method for very-large complexity problems in solid-state physics modeling. This is a rigorous mathematical solution, however it may not be the most elegant software solution. Good luck to you.

Answer 2

Interesting question. If on Linux, /dev/urandom or even /dev/random might suit. These devices rely on an "entropy pool," fed by the timing of asynchronous hardware events.

However, also investigate the mrand48() family of functions, presented in cstdlib or stdlib.h, whether or not on Linux. That gets you 48 bits, which is closer to what you want.

Good luck.