Re: Random array (fwd)
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 --'- --------------------------------------------------------------------
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 --'- --------------------------------------------------------------------
participants (2)
-
Jim Choate -
Yardena Arar + Christian Goetze