Re: Randomly outputting an array




On Sun, 16 Jul 2006, Logan Shaw wrote:
Ico wrote:
Ico <usenet@xxxxxxx> wrote:

Is N times swapping two elements considered enough to truly 'randomize'
an array ?

That was a stupid question, please ignore me...

Actually, it's not a stupid question. It's a very good question.
The answer is definitely "no".

No, the answer is "it depends."

My knee-jerk reaction was also "no", but then I realized that Ico was
replying to Richard Heathfield's post, which is an obvious "yes" (or
should be, if he didn't make any unnecessary mistakes).

Picking N pairs uniformly at random and swapping them will definitely
not shuffle the array, since there are (N^2)^N = N^(2N) ways to pick
N pairs, and N! ways to shuffle the array, and N^(2N) is generally not
a multiple of N!.

However, if you carefully pick those N pairs so that the first swap
swaps a random element into position 1, the second swap swaps a random
element /from those that remain/ into position 2, and so on, then that's
the "52-card pickup" algorithm, and it works fine. It's all in /which/
N pairs you swap.

If you don't pick your pairs carefully, according to some algorithm,
then you can keep swapping as long as you please, and the array will
never get perfectly shuffled. On the other hand, if your first N swaps
are according to the right algorithm, then you can make as many "wrong"
swaps as you like, afterwards, and the array won't get any less shuffled. :)

-Arthur
.