Thanks that looks like exactly what I wanted.  I'll play with it tomorrow.

  Thanks again,
Phil

William Chops Westfield wrote:

>
> On Jun 11, 2006, at 2:22 PM, Phil Keller wrote:
>
>>
>> I have an application that I need to generate a random number
>> sequence for.  Not just a random number, I know how to do that,
>> but an entire pseudo random sequence.
>
>
> You want a "shuffle" algorithm.  With a similar problem some time
> ago, I came up with this framework (in C):
>
> The enclosed code in shuffle_lib.c will return a shuffled sequence of any
> number of items up to 65535, using only 6 bytes or less of storage.  A
> pseudo-random number generator (PRNG) can be used to produce a 
> non-repeating
> sequence of numbers, but the usual implementation will generate only a
> sequence of length 2^N-1 (for an N bit number.)  That's not a problem, 
> you
> can just filter out all the numbers that are outside the range of 
> interest.
> The other problem with a PRN is that the sequence itself repeats; 12 
> always
> follows 232, or whatever.  Since our PRNG is generating a larger range 
> than
> we want anyway, this can be fixed by permuting the number somehow before
> filtering, using a separate permutation constant.  This means that our 
> final
> algorithm is something like:
>
>     shufflednum(max) = filter(max, permute(prng(randreg), permuteconst));
>
> The code example enclosed uses a standard shift-with-xor-feedback 
> scheme for
> the PRNG, simple subtraction for the permutation, and a test against the
> maximum as the filter, making it quite fast.  (however, it needs to be 
> fast
> if the number of items to be shuffled is much smaller than the size of 
> the
> PRNG.  to get 10 items with a 16 bit PRN, you may end up filtering out 
> 65525
> numbers.  This can be optimized by using a shorter PRN, of course.)  Note
> that by changing the PRNG seed, you change the starting position of the
> shuffled list, but not the list itself, while changing the permutation
> constant results in dramatically different sequences.
>
> Enclosed files:
>
> shuffle_lib.c: library functions in hopefully machine-independent C code
> shuffle_test.c: demonstration program, written for unix, tested on 
> Solaris
> shuffle_log.c: sample run, demonstrating effects of seed vs permutation
>                constant changes
>
>

-- 
--------------------------------
Long ago when men cursed and beat the 
ground with sticks,  it was called witchcraft..

Today, it's called golf.


-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist