From: Yardena Arar + Christian Goetze <kitties@best.com>
Date: Sat, 31 Oct 1998 02:55:20 +0800
To: Jim Choate <ravage@EINSTEIN.ssz.com>
Subject: Re: Random array (fwd)
In-Reply-To: <199810301748.LAA25557@einstein.ssz.com>
Message-ID: <Pine.BSF.4.05.9810300950020.17124-100000@shell5.ba.best.com>
MIME-Version: 1.0
Content-Type: text/plain



And what's so bad about doing this:

for (i=0; i < n-1; i++) {
  swap_positions(array, i, i+rand(n-i));
}

which populates the array by randomly choosing the next element?

It all comes down to knowing how good "rand()" is, anyway...


On Fri, 30 Oct 1998, Jim Choate wrote:

> 
> Forwarded message:
> 
> > Date: Fri, 30 Oct 1998 08:53:20 -0800
> > From: Jim Gillogly <jim@acm.org>
> > Subject: Re: Random array (fwd)
> 
> > Jim Choate responded:
> > > If I understand the process. Each array would cycle through in parallel
> > > sorting 2 elements of each array. Once that was finished we'd then sort the
> > > arrays themselves according to some process. From your description it seems
> > > to imply that you're going to sort the 1st element descending at that point.
> > > This in effect mis-orders each array after every sort.
> > >
> > > This sort of system is an IFS and could lead to determinism (ie a cycle of
> > > sort patterns that repeat endlessly) or chaos (ie a pattern that doesn't
> > > repeat). It in and of itself doesn't guarantee any randomness merely a
> > > continously munged sort.
> > 
> > I expressed myself badly.  Steve Gibbons posted a message
> > to Coderpunks expressing more clearly what I had in mind:
> > Fill up the high bits of your N words with random numbers and
> > the low bits with an index from 0 to N-1.  Sort the array, then
> > mask off the high bits.  If the random numbers were unique, you
> > are left with a randomly shuffled array.
> 
> Ah, ok I think I have it.....
> 
>  So we start out with N words (2 bytes):
> 
>    0  1  2  ...  n-2 n-1 n
>    *  *  *       *   *   *
> 
>    ^
>  15...8 7...0
>    rng   ind
> 
> So the ordering of bits 8-15 moves the originaly ordered indexes to
> positions correlated to relative magnitude of the rng part.
> 
> That certainly looks like it'd work.
> 
> Thanks for the clarification.
> 
> 
>     ____________________________________________________________________
>  
>        To know what is right and not to do it is the worst cowardice.
> 
>                                                      Confucius
> 
>        The Armadillo Group       ,::////;::-.          James Choate
>        Austin, Tx               /:'///// ``::>/|/      ravage@ssz.com
>        www.ssz.com            .',  ||||    `/( e\      512-451-7087
>                            -====~~mm-'`-```-mm --'-
>     --------------------------------------------------------------------
> 
>