# Re: Help: Randomizing a List of Numbers

**From:** Tim Smith (*reply_in_group_at_mouse-potato.com*)

**Date:** 07/22/04

**Next message:**thisisme_at_cotse.net: "Re: Block vs. Stream"**Previous message:**Bill Emerson: "Re: Help: Randomizing a List of Numbers"**In reply to:**Arthur J. O'Dwyer: "Re: Help: Randomizing a List of Numbers"**Next in thread:**David Wagner: "Re: Help: Randomizing a List of Numbers"**Reply:**David Wagner: "Re: Help: Randomizing a List of Numbers"**Reply:**Michael Amling: "Re: Help: Randomizing a List of Numbers"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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

**Next message:**thisisme_at_cotse.net: "Re: Block vs. Stream"**Previous message:**Bill Emerson: "Re: Help: Randomizing a List of Numbers"**In reply to:**Arthur J. O'Dwyer: "Re: Help: Randomizing a List of Numbers"**Next in thread:**David Wagner: "Re: Help: Randomizing a List of Numbers"**Reply:**David Wagner: "Re: Help: Randomizing a List of Numbers"**Reply:**Michael Amling: "Re: Help: Randomizing a List of Numbers"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]