Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23
Anonymous (nobody@replay.com)
Thu, 29 Oct 1998 19:22:52 +0100
For any N greater than two, the random-swap algorithm cannot produce
a perfectly smooth randomization of A[N].
A perfect randomization of A[N] would give equal probability to each of
the N! (N factorial) possible rearrangements of A. Note that for all N,
N! is a multiple of N-1.
Each iteration of the random-swap algorithm makes two choices of the N
values to swap. There are N^2 possible ways these two choices could go.
To calculate the probabilities after an iteration, we try all the N^2
choices and count how many instances of each arrangement are produced.
This gives each possible arrangement a probability in the form of
k/N^2, where k of the N^2 choices led to that arrangement.
After multiple iterations, we can calculate a similar probability, but the
denominator will be a power of N^2. After two iterations it is N^4, after
three iterations it is N^6, and after m iterations it is N^(2m).
If the result is to be perfectly random, each of the N factorial
arrangements must have equal probability. Suppose this happens after
m iterations. Let the probability of each arrangement be k/N^(2m).
These are all equal and there are N! arrangements, and they all add up
to 1 (since they are probabilities). Therefore (N! * k) / N^(2m) = 1,
and so N! * k = N^(2m). We see that The denominator of the fraction
must be a multiple of N factorial.
But for no N greater than two is any power of N a multiple of N factorial.
All such N are relatively prime to N-1. Therefore taking N to any power
will never produce a number which is a multiple of N-1, and so it cannot
be a multiple of N factorial. QED.
No matter how many times the swap is iterated, the result will never have
a perfectly even distribution over all N! possible arrangements. The
correct algorithm for randomizing an array is very simple and has already
been posted.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23