Re: Help: Randomizing a List of Numbers

From: Tim Smith (reply_in_group_at_mouse-potato.com)
Date: 07/22/04


Date: Thu, 22 Jul 2004 21:13:30 GMT

On 2004-07-22, Arthur J. O'Dwyer <ajo@nospam.andrew.cmu.edu> wrote:
> If you have a nicely random PRNG in 'rand()',[1] then this ought to be a
> nicely random shuffle. I don't know why you even bothered with the /two/
> calls to 'qsort' in your function; surely one is enough, theoretically
> speaking?[2]
>
> ...On second thought, there's not enough specified about 'qsort' to say
> for sure. 'qsort' is not guaranteed to be a stable sort, but if it is
> [not an outlandish assumption], then both functions are not random
> shuffles --- consider what happens in the (non-conforming) pathological
> case where RAND_MAX is 1 or 2, and then notice that the effect doesn't
> completely go away even when RAND_MAX is 32767.

You've figured out what I was worried about. Suppose, for example, 5
numbers in the array get 17 from the PRNG. Then, those 5 numbers will be
brought together, but their order probably won't be randomized. They will
be in the original order if the sort is stable, and even if the sort is not
stable, it probably isn't random.

On the second pass, it is very unlikely that those 5 numbers will again be
given matching numbers from the PRN. They are most likely to get 5
different PRNs. So, they will end up randomized after the second pass.

Note that if a given pair of numbers are randomized after the first pass,
they stay randomized after the second pass, even if they are assigned the
same PRN in the second pass.

Basically, for a given two numbers to not end up randomized after two
passed, they need to have a PRN match in the first pass, and another PRN
match in the secon pass.

Without doing any actual analysis, my guess was that two passes would be
enough.

I suppose another approach would be to do one pass, then go through and find
the groups that were assigned matching PRNs, and recursively randomize those
subarrays.

-- 
--Tim Smith