Re: Re: RANDOM function?

On Tue, 31 Jul 2001, Einar Karttunen wrote:
> On Tue, 31 Jul 2001 ghaverla@freenet.edmonton.ab.ca wrote:
> > On Tue, 31 Jul 2001, macky wrote:
> >
> > > if ill be using big range of numbers sa 10000 woundd the be any possibility
> > > to have multiple items... meaning lets say 1234 will show up more than once?
> >
> > It sounds like you are trying to draw a number from a finite
> > supply, WITHOUT REPLACEMENT.

> That sounds very hard to implement effeciently. Could you send me some
> high level pseudocode? I think that a with 31 bit random integers the
> probablity to get the same value is very very small. If it is too big
> I can always change to bigints.

I'm sure you can do a search for a RNG without replacement as
easily as I can.  Yes, a person can always keep track of what
numbers have already been picked and reject duplicate picks.
If the number of picks you are making is much smaller than the
space you are picking from, this would work fine.  Especially
using a smart (not linear) search for the possible duplicate.
If the number of picks is getting close to the size of the
stack, rejection is going to be a big loser.  Any program
that draws cards from a deck is going to use this type of
without replacement method, as some card games deal the entire
deck.

Gord

Matter Realisations     http://www.materialisations.com/
Gordon Haverland, B.Sc. M.Eng. President
101  9504 182 St. NW    Edmonton, AB, CA  T5T 3A7
780/481-8019            ghaverla @ freenet.edmonton.ab.ca
780/993-1274 (cell)