usenet@cps3xx.UUCP (Usenet file owner) (05/19/89)
First I would like to thank everyone who replied. I now have a large
collection of these algorithms, so I can choose the one best suited to
my particular needs.
I received about 30 replies, but most of these were minor variations on
a more general group of 3. Here are the three general algorithms for an
array of n elements:
(1) For each element in the array, generate a random number between
1 and m, where m is much larger than n. Then sort the array
using these random numbers as the key.
(2) Generate pairs of random numbers between 1 and n and swap the
elements at these locations, repeating this enough to get the
array scrambled.
(3) For each element in the array, randomly choose a "partner" and
swap them. This solution was the most common, and IMHO the
most straightforward and easiest to implement. I liked the
version sent to me by Rick Schubert (rns@se-sd.sandiego.NCR.COM)
the most, and here it is:
> This version permutes the array (named "array") in place, rather than
> generating the auxiliary "list" array.
>
> for i = 1 to n-1
> {
> x = random number between i and n
> /* now interchange array[i] and array[x] */
> temp = array[i]
> array[i] = array[x]
> array[x] = temp
> }
>
> Notice that x is chosen between "i" and n, NOT between 1 and n. This is
> crucial if you want all possible permutations to be equally likely.
>
> -- Rick Schubert (rns@se-sd.sandiego.NCR.COM)
If anyone would like more information or the code for these algorithms,
feel free to drop me a line.
Paul Reed
Internet: reedp@horus.cem.msu.edu Bitnet: reedp@MSUCEM