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
.



Relevant Pages

  • Re: sorting an array of three kinds of stones
    ... The worst case is 2/3N swaps. ... the algorithm scans the array 4 times; ... Given an array of 3 values (types of stones), sort the array, ... void Myswitch(int * stone, int a, int b) ...
    (comp.programming)
  • Re: OCAML versus Scheme versus Clean
    ... an array that does not require too many swaps. ... I required Bigloo to check array bonds. ... a 64 bit machine does speed up OCAML, but it speeds up Bigloo too. ...
    (comp.lang.functional)
  • Re: OCAML versus Scheme versus Clean
    ... an array that does not require too many swaps. ... I required Bigloo to check array bonds. ... to something closer to the OCAML speed. ...
    (comp.lang.functional)
  • Re: Random reordering of a list
    ... >possible ways that the algorithm can proceed is six. ... swaps it with a random element in the entire array. ... this algorithm with a few billion iterations and the distribution ...
    (sci.stat.math)
  • Re: Random reordering of a list
    ... > swaps it with a random element in the entire array. ... > this algorithm with a few billion iterations and the distribution ... Generating random permutations is an important little problem ...
    (sci.stat.math)