[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Random array (fwd)
Forwarded message:
> Date: Fri, 30 Oct 1998 08:53:20 -0800
> From: Jim Gillogly <[email protected]>
> 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 /:'///// ``::>/|/ [email protected]
www.ssz.com .', |||| `/( e\ 512-451-7087
-====~~mm-'`-```-mm --'-
--------------------------------------------------------------------