Xref: utzoo comp.sources.wanted:7453 alt.msdos.programmer:55
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!uwvax!tank!eecae!cps3xx!usenet
From: usenet@cps3xx.UUCP (Usenet file owner)
Newsgroups: comp.sources.wanted,alt.msdos.programmer
Subject: Summary and thanks for scramble algorithms
Keywords: random, scramble, algorithm, shuffle
Message-ID: <3034@cps3xx.UUCP>
Date: 18 May 89 20:22:17 GMT
Reply-To: reedp@frith.egr.msu.edu ()
Organization: Michigan State University, Engineering, E. Lansing
Lines: 44

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